POJ 2003 - Hire and Fire

http://poj.org/problem?id=2003

概要

ある組織の階層構造をシミュレートする．

ある一人の人物からスタートし，

• x が y を雇う
• x を解雇する
• 現在の状況を出力する

の3種類のクエリを処理する．

x が y を雇うとき，x の子ノードとして y を一番右に追加する．

x を解雇するとき，もし x に子ノードがいなかった場合は，単に x のノードを削除する． x に子ノードがいた場合は，x の子ノードのうち最も左にある y を x の位置に移動させ， 再帰的に y について同様の操作を行う．

現在の状況を出力するときは，サンプル出力にあるように出力する．

制約

• 名前は2文字以上20文字以下で，空白を含まない
• どんなときでも少なくとも1人は組織に存在する
• 1000人より多く組織に存在するときはない

解法

実装ゲー．

子ノードを deque で持ち，雇用のときは単に push_back し，x を解雇するときは子ノードの先頭と名前を swap し， 再帰的に処理した後，子ノードに x がいたら erase する，というように実装した．

 1 #include <iostream>
 2 #include <deque>
 3 using namespace std;
 4 
 5 struct tree
 6 {
 7   string name;
 8   deque<tree> cs;
 9   tree(const string& s) : name(s), cs() {}
10 
11   void print(int depth = 0) const
12   {
13     for (int i = 0; i < depth; i++) {
14       cout << "+";
15     }
16     cout << name << endl;
17     for (deque<tree>::const_iterator it(cs.begin()); it != cs.end(); ++it) {
18       it->print(depth+1);
19     }
20   }
21 
22   void fire(const string& victim)
23   {
24     if (name == victim) {
25       if (!cs.empty()) {
26         swap(name, cs[0].name);
27         cs[0].fire(victim);
28       }
29     } else {
30       for (deque<tree>::iterator it = cs.begin(); it != cs.end(); ++it) {
31         it->fire(victim);
32       }
33     }
34     for (deque<tree>::iterator it = cs.begin(); it != cs.end(); ++it) {
35       if (it->name == victim) {
36         cs.erase(it);
37         return;
38       }
39     }
40   }
41 
42   bool hire(const string& boss, const string& s)
43   {
44     if (boss == name) {
45       cs.push_back(tree(s));
46       return true;
47     } else {
48       for (deque<tree>::iterator it = cs.begin(); it != cs.end(); ++it) {
49         if (it->hire(boss, s)) {
50           return true;
51         }
52       }
53     }
54     return false;
55   }
56 };
57 
58 int main()
59 {
60   string name;
61   cin >> name;
62   tree root(name);
63   while (cin >> name) {
64     if (name == "print") {
65       root.print();
66       cout << "------------------------------------------------------------" << endl;
67     } else if (name == "fire") {
68       cin >> name;
69       root.fire(name);
70     } else {
71       string t;
72       cin >> t >> t;
73       root.hire(name, t);
74     }
75   }
76   return 0;
77 }