Advertisement
Guest User

lobinhos

a guest
Oct 13th, 2019
98
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.94 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define INF 1000000000
  5. #define mp make_pair
  6. #define pb push_back
  7. #define st first
  8. #define nd second
  9. #define FOR(i,a,b) for(int (i) = (a); (i) < (b); (i)++)
  10. #define sz(X) (int)(X).size()
  11. typedef pair<int, int> ii;
  12. typedef vector<ii> vii;
  13. typedef vector<int> vi;
  14.  
  15. int main(){
  16.     int n;
  17.     int ans = 0;
  18.     cin >> n;
  19.     vii votos;
  20.     FOR(i,0,n){
  21.         int a, b;
  22.         scanf("%d%d", &a, &b);
  23.         votos.pb(mp(a-1,b-1));
  24.     }
  25.  
  26.     FOR(lobo, 0, n){
  27.         int v_lobo = 0;
  28.         set<int> votaram;
  29.         votaram.insert(lobo);
  30.         FOR(i,0,n){
  31.             if(i == lobo) continue;
  32.             ii curr = votos[i];
  33.             if(curr.st == lobo || curr.nd == lobo){
  34.                 v_lobo++;
  35.                 votaram.insert(i);
  36.             }
  37.         }
  38.         set<int> to_vote;
  39.         FOR(i,0,n){
  40.             if(votaram.count(i) == 0) to_vote.insert(i);
  41.         }
  42.         vi hp(n, v_lobo);
  43.         hp[lobo] = 0;
  44.         hp[votos[lobo].st]--;
  45.         hp[votos[lobo].nd]--;
  46.  
  47.         if(hp[votos[lobo].st] <= 0 || hp[votos[lobo].nd] <= 0){
  48.             ans++;
  49.             continue;
  50.         }
  51.  
  52.         vector<bool> safe(n, false);
  53.  
  54.         safe[lobo] = true;
  55.        
  56.         while(true){
  57.             vi freq(n, 0);
  58.             for(int i : to_vote){
  59.                 ii curr = votos[i];
  60.                 freq[curr.st]++;
  61.                 freq[curr.nd]++;
  62.             }
  63.  
  64.             int mini = INF, minind = -1;
  65.             FOR(i,0,n){
  66.                 if(safe[i]) continue;
  67.                 if(freq[i] < hp[i]){
  68.                     if(freq[i] < mini){
  69.                         mini = freq[i];
  70.                         minind = i;
  71.                     }
  72.                 }
  73.             }
  74.            
  75.             if(mini == INF) break;
  76.  
  77.             set<int> to_erase;
  78.  
  79.             for(int i: to_vote){
  80.                 ii curr = votos[i];
  81.                 if(curr.st == minind || curr.nd == minind){
  82.                     to_erase.insert(i);
  83.                 }
  84.             }
  85.             for(int i: to_erase){
  86.                 to_vote.erase(i);
  87.                 hp[minind]--;
  88.             }
  89.             safe[minind] = true;
  90.         }
  91.        
  92.         for(int i : hp){
  93.             //cout << i << " ";
  94.         }
  95.         //cout << endl;
  96.  
  97.         if(sz(to_vote) == 0) continue;
  98.  
  99.         int sobra = sz(to_vote);
  100.         int not_safe_hp = 0;
  101.         FOR(i,0,n){
  102.             if(!safe[i]) not_safe_hp+=(hp[i]-1);
  103.         }
  104.  
  105.         if(sobra > not_safe_hp){
  106.             ans++;
  107.         }
  108.     }
  109.  
  110.     cout << ans << endl;
  111.  
  112.     return 0;
  113. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement