Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define INF 1000000000
- #define mp make_pair
- #define pb push_back
- #define st first
- #define nd second
- #define FOR(i,a,b) for(int (i) = (a); (i) < (b); (i)++)
- #define sz(X) (int)(X).size()
- typedef pair<int, int> ii;
- typedef vector<ii> vii;
- typedef vector<int> vi;
- int main(){
- int n;
- int ans = 0;
- cin >> n;
- vii votos;
- FOR(i,0,n){
- int a, b;
- scanf("%d%d", &a, &b);
- votos.pb(mp(a-1,b-1));
- }
- FOR(lobo, 0, n){
- int v_lobo = 0;
- set<int> votaram;
- votaram.insert(lobo);
- FOR(i,0,n){
- if(i == lobo) continue;
- ii curr = votos[i];
- if(curr.st == lobo || curr.nd == lobo){
- v_lobo++;
- votaram.insert(i);
- }
- }
- set<int> to_vote;
- FOR(i,0,n){
- if(votaram.count(i) == 0) to_vote.insert(i);
- }
- vi hp(n, v_lobo);
- hp[lobo] = 0;
- hp[votos[lobo].st]--;
- hp[votos[lobo].nd]--;
- if(hp[votos[lobo].st] <= 0 || hp[votos[lobo].nd] <= 0){
- ans++;
- continue;
- }
- vector<bool> safe(n, false);
- safe[lobo] = true;
- while(true){
- vi freq(n, 0);
- for(int i : to_vote){
- ii curr = votos[i];
- freq[curr.st]++;
- freq[curr.nd]++;
- }
- int mini = INF, minind = -1;
- FOR(i,0,n){
- if(safe[i]) continue;
- if(freq[i] < hp[i]){
- if(freq[i] < mini){
- mini = freq[i];
- minind = i;
- }
- }
- }
- if(mini == INF) break;
- set<int> to_erase;
- for(int i: to_vote){
- ii curr = votos[i];
- if(curr.st == minind || curr.nd == minind){
- to_erase.insert(i);
- }
- }
- for(int i: to_erase){
- to_vote.erase(i);
- hp[minind]--;
- }
- safe[minind] = true;
- }
- for(int i : hp){
- //cout << i << " ";
- }
- //cout << endl;
- if(sz(to_vote) == 0) continue;
- int sobra = sz(to_vote);
- int not_safe_hp = 0;
- FOR(i,0,n){
- if(!safe[i]) not_safe_hp+=(hp[i]-1);
- }
- if(sobra > not_safe_hp){
- ans++;
- }
- }
- cout << ans << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement