Guest User

Untitled

a guest
Mar 1st, 2011
157
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.  USER: pdp23u8
  3.  NAME: Loukas Xanthos
  4.  LANG: C++
  5.  TASK: company
  6.  COMMENTS: pdp23 part 2 (High School)
  7. */
  8.  
  9. #include <iostream>
  10. #include <fstream>
  11. #include <vector>
  12. using namespace std;
  13.  
  14. #define MAX_N 400002
  15.  
  16. #define F false
  17. #define M true
  18.  
  19. typedef unsigned long int uint;
  20. uint N, boss;
  21. long int diff;
  22. vector<uint> graph[MAX_N];
  23. vector<bool> sex(MAX_N);
  24.  
  25. void DFS(uint node, uint females, uint males)
  26. {
  27.    
  28.     if(sex[node] == F) {
  29.         diff += males;
  30.         females++;
  31.     }
  32.     else if(sex[node] == M) {
  33.         diff -= females;
  34.         males++;
  35.     }
  36.    
  37.     for(register uint i = 0; i < (uint) graph[node].size(); i++) {
  38.         DFS(graph[node][i], females, males);
  39.     }
  40. }
  41.  
  42. int main()
  43. {
  44.     ifstream fin("company.in");
  45.     ofstream fout("company.out");
  46.      
  47.     fin >> N;
  48.     for(register uint i = 1; i <= N; i++)
  49.     {
  50.         uint sup;
  51.         char tmps;
  52.         fin >> sup;
  53.         fin >> tmps;
  54.  
  55.         if(tmps == 'f')
  56.             sex[i] = F;
  57.         else
  58.             sex[i] = M;
  59.         if(sup == 0)
  60.             boss = i;
  61.         else
  62.             graph[sup].push_back(i);
  63.     }
  64.      
  65.     DFS(boss, 0, 0);
  66.    
  67.     fout << diff << '\n';
  68.     fin.close();
  69.     fout.close();
  70.     return 0;
  71. }
RAW Paste Data