ural 1242. Werewolf

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cstdlib>
  4 #include <cmath>
  5 #include <deque>
  6 #include <vector>
  7 #include <queue>
  8 #include <iostream>
  9 #include <algorithm>
 10 #include <map>
 11 #include <set>
 12 #include <ctime>
 13 #include <iomanip>
 14 using namespace std;
 15 typedef long long LL;
 16 typedef double DB;
 17 #define For(i, s, t) for(int i = (s); i <= (t); i++)
 18 #define Ford(i, s, t) for(int i = (s); i >= (t); i--)
 19 #define Rep(i, t) for(int i = (0); i < (t); i++)
 20 #define Repn(i, t) for(int i = ((t)-1); i >= (0); i--)
 21 #define rep(i, x, t) for(int i = (x); i < (t); i++)
 22 #define MIT (2147483647)
 23 #define INF (1000000001)
 24 #define MLL (1000000000000000001LL)
 25 #define sz(x) ((int) (x).size())
 26 #define clr(x, y) memset(x, y, sizeof(x))
 27 #define puf push_front
 28 #define pub push_back
 29 #define pof pop_front
 30 #define pob pop_back
 31 #define ft first
 32 #define sd second
 33 #define mk make_pair
 34 inline void SetIO(string Name)
 35 {
 36     string Input = Name+".in",
 37     Output = Name+".out";
 38     freopen(Input.c_str(), "r", stdin),
 39     freopen(Output.c_str(), "w", stdout);
 40 }
 41 
 42 inline bool Getint(int &Ret)
 43 {
 44     Ret = 0;
 45     char Ch = ‘ ‘;
 46     bool Flag = 0;
 47     while(!(Ch >= ‘0‘ && Ch <= ‘9‘))
 48     {
 49         if(Ch == ‘B‘) Flag = 1;
 50         if(Flag == 1 && Ch == ‘D‘) break;
 51         Ch = getchar();
 52     }
 53     if(Flag) return 0;
 54     while(Ch >= ‘0‘ && Ch <= ‘9‘)
 55     {
 56         Ret = Ret * 10 + Ch - ‘0‘;
 57         Ch = getchar();
 58     }
 59     return 1;
 60 }
 61 
 62 const int N = 1010;
 63 int n;
 64 vector<int> Parent[N], Child[N], Ans;
 65 bool Visit[N];
 66 
 67 inline void Input() 
 68 {
 69     scanf("%d", &n);
 70     int x, y;
 71     while(Getint(x))
 72     {
 73         Getint(y);
 74         Parent[x].pub(y), Child[y].pub(x);
 75     }
 76 }
 77 
 78 inline void GoUp(int x)
 79 {
 80     Visit[x] = 1;
 81     int Length = sz(Parent[x]);
 82     Rep(i, Length) GoUp(Parent[x][i]);
 83     Parent[x].clear();
 84 }
 85 
 86 inline void GoDown(int x)
 87 {
 88     Visit[x] = 1;
 89     int Length = sz(Child[x]);
 90     Rep(i, Length) GoDown(Child[x][i]);
 91     Child[x].clear();
 92 }
 93 
 94 inline void Solve()
 95 {
 96     int x;
 97     while(~scanf("%d", &x))
 98     {
 99         GoUp(x);
100         GoDown(x);
101     }
102     
103     For(i, 1, n)
104         if(!Visit[i]) Ans.pub(i);
105     if(sz(Ans))
106     {
107         Rep(i, sz(Ans)-1) printf("%d ", Ans[i]);
108         printf("%d\n", Ans.back());
109     }
110     else puts("0");
111 }
112 
113 int main()
114 {
115     #ifndef ONLINE_JUDGE 
116     SetIO("A");
117     #endif 
118     Input();
119     Solve();
120     return 0;
121 }