Advertisement
nullzero

C

Jul 30th, 2012
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.12 KB | None | 0 0
  1. #include <cstdio>
  2. #include <vector>
  3. #include <set>
  4.  
  5. const int N(500);
  6.  
  7. using namespace std;
  8. typedef pair<int,int> II;
  9. typedef set<II>::iterator iter;
  10.  
  11. set<II> group[3];
  12. int remain[N], revtype[N], temremain[N];
  13. vector<int> type[3];
  14. vector<int> pre[N];
  15.  
  16. int main(){
  17.     int n;
  18.     scanf("%d", &n);
  19.     for(int i = 0; i < n; ++i){
  20.         int t;
  21.         scanf("%d", &t);
  22.         --t;
  23.         type[t].push_back(i);
  24.         revtype[i] = t;
  25.     }
  26.     for(int i = 0; i < n; ++i){
  27.         scanf("%d", &temremain[i]);
  28.        
  29.         for(int j = 0; j < temremain[i]; ++j){
  30.             int val;
  31.             scanf("%d", &val);
  32.             --val;
  33.             pre[val].push_back(i);
  34.         }
  35.     }
  36.     int vmin = 999999999;
  37.     for(int start = 0; start < 3; ++start){
  38.         group[0].clear();
  39.         group[1].clear();
  40.         group[2].clear();
  41.         for(int i = 0; i < n; ++i){
  42.             remain[i] = temremain[i];
  43.             group[revtype[i]].insert(II(remain[i], i));
  44.         }
  45.         int complete = 0;
  46.         int now = start;
  47.         int cnt = 0;
  48.         while(complete < n){
  49.             iter i = group[now].begin();
  50.             while(i != group[now].end()){
  51.                 if(i->first != 0) break;
  52.                 //printf("finish %d at %d\n", i->second, now);
  53.                 for(int j = 0; j < pre[i->second].size(); ++j){
  54.                     int al = pre[i->second][j];
  55.                     //printf("help %d to %d\n", al, remain[al] - 1);
  56.                     iter it = group[revtype[al]].find(II(remain[al], al));
  57.                     group[revtype[al]].erase(it);
  58.                     --remain[al];
  59.                     group[revtype[al]].insert(II(remain[al], al));
  60.                     //printf("at %d (%d,%d)\n", revtype[al], remain[al], al);
  61.                 }
  62.                 group[now].erase(i);
  63.                 i = group[now].begin();
  64.                 cnt++;
  65.                 complete++;
  66.             }
  67.             now++;
  68.             now %= 3;
  69.             cnt++;
  70.         }
  71.         vmin = min(vmin, cnt - 1);
  72.         //printf("%d\n", cnt - 1);
  73.     }
  74.     printf("%d\n", vmin);
  75.     return 0;
  76. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement