Submission #421038

#TimeUsernameProblemLanguageResultExecution timeMemory
421038faresbasbsFriend (IOI14_friend)C++14
0 / 100
1 ms332 KiB
#include <bits/stdc++.h> #include "friend.h" using namespace std; vector<int> graph[1001]; vector<bool> used; int n,k,val[1001]; bool which[1001]; vector<int> mt; bool try_kuhn(int v) { if (used[v]) return false; used[v] = true; for (int to : graph[v]) { if (mt[to] == -1 || try_kuhn(mt[to])) { mt[to] = v; return true; } } return false; } int findSample(int N , int confidence[] , int host[] , int protocol[]){ which[0] = 0 , val[0] = 0; n = 1 , k = 0; for(int i = 1 ; i < N ; i += 1){ if(protocol[i] == 0){ which[i] = 1-which[host[i]]; if(which[i] == 0){ val[i] = n++; graph[val[i]].push_back(val[host[i]]); }else{ val[i] = k++; graph[val[host[i]]].push_back(val[i]); } }else{ which[i] = which[host[i]]; if(which[i] == 0){ val[i] = n++; }else{ val[i] = k++; } for(auto j : graph[val[host[i]]]){ if(which[j] == 0){ graph[j].push_back(val[i]); }else{ graph[val[i]].push_back(j); } } } } mt.assign(k, -1); vector<bool> used1(n, false); for (int v = 0; v < n; ++v) { for (int to : graph[v]) { if (mt[to] == -1) { mt[to] = v; used1[v] = true; break; } } } for (int v = 0; v < n; ++v) { if (used1[v]) continue; used.assign(n, false); try_kuhn(v); } int mx = 0; for(int i = 0 ; i < k ; i += 1){ mx = max(mx,mt[i]+1); } return N-mx; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...