fork(2) download
copy 
  1. // iostream is too mainstream
  2. #include <cstdio>
  3. // bitch please
  4. #include <iostream>
  5. #include <vector>
  6. #include <set>
  7. #include <map>
  8. #include <string>
  9. #include <queue>
  10. #include <stack>
  11. #include <algorithm>
  12. #include <iomanip>
  13. #define dibs reserve
  14. #define OVER9000 1234567890
  15. #define patkan 9
  16. #define tisic 47
  17. #define soclose 10e-7
  18. #define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
  19. #define chocolate win
  20. #define ff first
  21. #define ss second
  22. #define abs(x) ((x < 0)?-(x):(x))
  23. // mylittlepony
  24. using namespace std;
  25.  
  26. int main() {
  27.     cin.sync_with_stdio(0);
  28.     int N,a,b;
  29.     cin >> N;
  30.     vector< vector<int> > son(N);
  31.     vector<int> par(N,-1);
  32.     vector<int> state(N,0);
  33.     string s;
  34.     cin >> s;
  35.     for(int i =0; i < N; i++) {
  36.     	if(s[i] == '+') state[i] =1;
  37.     	if(s[i] == '-') state[i] =-1;}
  38.     if(state[0] == 0) state[0] =-1;
  39.     for(int i =1; i < N; i++) {
  40.     	cin >> a >> b;
  41.     	par[--b] =--a;
  42.     	son[a].push_back(b);}
  43.  
  44.     // dorataj state
  45.     queue<int> q;
  46.     q.push(0); par[0] =0;
  47.     vector<bool> live(N,true); live[0] =false;
  48.     vector<int> ord(1,0);
  49.     while(!q.empty()) {
  50.     	a =q.front();
  51.     	ALL_THE(son[a],it) if(live[*it]) {
  52.     		live[*it] =false;
  53.     		q.push(*it);
  54.     		ord.push_back(*it);
  55.     		if(state[*it] == 0) state[*it] =state[a];}
  56.     	q.pop();}
  57.  
  58.     vector<bool> allA(N,true);
  59.     for(int i =N-1; i >= 0; i--) {
  60.     	a =ord[i];
  61.     	ALL_THE(son[a],it) if(!allA[*it]) allA[a] =false;
  62.     	if(son[a].empty() && state[a] == -1) allA[a] =false;}
  63.  
  64.     a =0;
  65.     for(int i =0; i < N; i++) 
  66.     	if(allA[i] && (i == 0 || !allA[par[i]])) a++;
  67.     cout << a << "\n";
  68.     for(int i =0; i < N; i++) if(allA[i] && (i == 0 || !allA[par[i]])) {
  69.     		cout << i+1;
  70.     		a--;
  71.     		if(a > 0) cout << " ";}
  72. 	cout << "\n";
  73. 	return 0;}
  74.  
  75. // look at my code
  76. // my code is amazing
Success #stdin #stdout 0s 3440KB
comments (?)
stdin
copy 
10
+-+000++-+
1 2
1 5
1 9
2 6
2 8
5 4
5 10
9 3
9 7
stdout
copy 
3
5 8 9
https://ideone.com/pX2zeL
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!