Submission #436697

#TimeUsernameProblemLanguageResultExecution timeMemory
436697ScarletSFriend (IOI14_friend)C++17
0 / 100
1 ms344 KiB
#include <bits/stdc++.h> #define ll long long #define sz(x) (int)(x).size() using namespace std; const int N = 1005; int mt[N]; vector<int> e[N], v[2]; bitset<N> done, cmp; void dfs(int c, int x) { v[x].push_back(c); mt[c]=-1; cmp[c]=1; for (int i : e[c]) if (!cmp[i]) dfs(i,x^1); } bool try_kuhn(int c) { if (done[c]) return 0; done[c]=1; for (int i : e[c]) if (mt[i]==-1||try_kuhn(mt[i])) { mt[i]=c; return 1; } return 0; } int findSample(int n, int confidence[], int host[], int protocol[]) { for (int i=1;i<n;++i) { if (protocol[i]==0) { e[i].push_back(host[i]); e[host[i]].push_back(i); } else { for (int j : e[host[i]]) { e[i].push_back(j); e[j].push_back(i); } } } int tot=0, cur; for (int i=0;i<n;++i) if (!cmp[i]) { v[0].clear(); v[1].clear(); dfs(i,0); for (int j : v[0]) { done.reset(); try_kuhn(j); } cur=0; for (int j : v[1]) if (mt[j]!=1) ++cur; tot+=-cur+v[0].size()+v[1].size(); } return tot; }
#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...