Sharif ICPC Regionals 2006 - Problem D

   1:#include <map>
   2:#include <string>
   3:#include <vector>
   4:#include <fstream>
   5:#include <iomanip>
   6:#include <iostream>
   7:#include <algorithm>
   8:
   9:using namespace std;
  10:
  11:#define PROB_NAME   "D"
  12:
  13:struct Emp
  14:{
  15:    pair<int, bool> data [2];   
  16:    Emp () {data[0].first = -1; data[0].second = true; data[1].first = -1; data[1].second = true;}
  17:};
  18:
  19:pair<int, bool> Q (int cur, const vector<vector<int> > & children, vector<Emp> & mem);
  20:
  21:pair<int, bool> P (int cur, const vector<vector<int> > & children, vector<Emp> & mem)
  22:{
  23:    if (mem[cur].data[0].first >= 0) return mem[cur].data[0];
  24:    
  25:    pair<int, bool> ret (1, true);
  26:    for (unsigned i = 0; i < children[cur].size(); ++i)
  27:    {
  28:        pair<int, bool> r = Q(children[cur][i], children, mem);
  29:        ret.first += r.first;
  30:        ret.second = (ret.second && r.second);
  31:    }
  32:    return mem[cur].data[0] = ret;
  33:}
  34:
  35:pair<int, bool> Q (int cur, const vector<vector<int> > & children, vector<Emp> & mem)
  36:{
  37:    if (mem[cur].data[1].first >= 0) return mem[cur].data[1];
  38:    
  39:    pair<int, bool> ret (0, true);
  40:    for (unsigned i = 0; i < children[cur].size(); ++i)
  41:    {
  42:        pair<int, bool> rp = P(children[cur][i], children, mem);
  43:        pair<int, bool> rq = Q(children[cur][i], children, mem);
  44:        
  45:        ret.first += max (rp.first, rq.first);
  46:        if (rp.first > rq.first) ret.second = (ret.second && rp.second);
  47:        else if (rp.first < rq.first) ret.second = (ret.second && rq.second);
  48:        else ret.second = false;
  49:    }
  50:    return mem[cur].data[1] = ret;
  51:}
  52:
  53:int main ()
  54:{
  55:    ifstream fin (PROB_NAME ".in");
  56:    
  57:    int n;
  58:    while (fin >> n && n != 0)
  59:    {
  60:        map<string, int> empnum;
  61:        #define EMPNUM(name)    ((empnum.find(name) == empnum.end()) ? empnum[name] = (int)empnum.size() - 1 : empnum[name])
  62:
  63:        vector<int> parent (n, -1);
  64:        vector<vector<int> > children (n);
  65:
  66:        string foo, bar;
  67:        fin >> foo;
  68:        
  69:        empnum[foo] = 0;
  70:        for (int i = 1; i < n; ++i)
  71:        {
  72:            fin >> foo >> bar;
  73:            parent[EMPNUM(foo)] = EMPNUM(bar);
  74:            children[EMPNUM(bar)].push_back (EMPNUM(foo));
  75:        }
  76:        
  77:        vector<Emp> mem (n);
  78:        pair<int, bool> rp = P (0, children, mem);
  79:        pair<int, bool> rq = Q (0, children, mem);
  80:        
  81:        cout 
  82:            << max(rp.first, rq.first) << " "
  83:            << ((rp.first == rq.first ||
  84:                (rp.first > rq.first && !rp.second) ||
  85:                (rq.first > rp.first && !rq.second)
  86:                ) ? "NO" : "YES") << endl;
  87:        cout << rp.first << ", " << rp.second << ", " << rq.first << ", " << rq.second << endl;
  88:    }
  89:    
  90:    return 0;
  91:}
  92: