Guest User

Untitled

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