Task: | Factory |
Sender: | Game of Nolife |
Submission time: | 2017-05-27 12:41:22 +0300 |
Language: | C++ |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.06 s | details |
#2 | ACCEPTED | 0.04 s | details |
#3 | ACCEPTED | 0.06 s | details |
#4 | ACCEPTED | 0.13 s | details |
#5 | ACCEPTED | 0.16 s | details |
#6 | ACCEPTED | 0.12 s | details |
#7 | ACCEPTED | 0.14 s | details |
#8 | ACCEPTED | 0.10 s | details |
#9 | ACCEPTED | 0.12 s | details |
#10 | ACCEPTED | 0.10 s | details |
#11 | ACCEPTED | 0.14 s | details |
#12 | ACCEPTED | 0.14 s | details |
#13 | ACCEPTED | 0.16 s | details |
#14 | ACCEPTED | 0.12 s | details |
#15 | ACCEPTED | 0.12 s | details |
#16 | ACCEPTED | 0.05 s | details |
#17 | ACCEPTED | 0.04 s | details |
Code
#include <bits/stdc++.h>#define F first#define S second#define X real()#define Y imag()using namespace std;typedef long long ll;typedef long double ld;vector<int> g1[555];int r[555][555];int u[555];int git=1;void dfs(int x, int s){if (u[x]==git) return;r[s][x]=1;u[x]=git;for (int nx:g1[x]){dfs(nx, s);}}struct Matching{int n;vector<int> vLabel,ma,s,u;queue<int> q;void rm(int x, int y){int m=ma[x];ma[x]=y;if (ma[m]==x){if (vLabel[x]<=n){ma[m]=vLabel[x];rm(vLabel[x], m);}else{int a=1+(vLabel[x]-n-1)/n;int b=1+(vLabel[x]-n-1)%n;rm(a, b);rm(b, a);}}}void tr(int x){for (int i=1;i<=n;i++){s[i]=ma[i];}rm(x, x);for (int i=1;i<=n;i++){if (ma[i]!=s[i]) u[i]++;ma[i]=s[i];}}void rl(int x, int y){for (int i=1;i<=n;i++){u[i]=0;}tr(x);tr(y);for (int i=1;i<=n;i++){if (u[i]==1&&vLabel[i]<0){vLabel[i]=n+x+(y-1)*n;q.push(i);}}}int solve(vector<int>* g){for (int i=1;i<=n;i++){if (ma[i]==0){for (int j=1;j<=n;j++){vLabel[j]=-1;}vLabel[i]=0;q.push(i);while (!q.empty()){int x=q.front();q.pop();for (int y:g[x]){if (ma[y]==0&&i!=y){ma[y]=x;rm(x, y);while (!q.empty()) q.pop();break;}if (vLabel[y]>=0){rl(x, y);continue;}if (vLabel[ma[y]]<0) {vLabel[ma[y]]=x;q.push(ma[y]);}}}}}int res=0;for (int i=1;i<=n;i++) if (ma[i]>i) res++;return res;}Matching(int nn) : n(nn), vLabel(n+1), ma(n+1), s(n+1), u(n+1) {}};vector<int> g[555];int main(){ios_base::sync_with_stdio(0);cin.tie(0);int n,m;cin>>n>>m;for (int i=0;i<m;i++){int a,b;cin>>a>>b;g1[a].push_back(b);}for (int i=1;i<=n;i++){git++;dfs(i, i);}for (int i=1;i<=n;i++){for (int ii=i+1;ii<=n;ii++){if (r[i][ii]==0&&r[ii][i]==0){g[i].push_back(ii);g[ii].push_back(i);}}}Matching ma(n);int mm=ma.solve(g);assert(mm*2<=n);cout<<mm+n-mm*2<<endl;}
Test details
Test 1
Verdict: ACCEPTED
input |
---|
1 0 |
correct output |
---|
1 |
user output |
---|
1 |
Test 2
Verdict: ACCEPTED
input |
---|
2 0 |
correct output |
---|
1 |
user output |
---|
1 |
Test 3
Verdict: ACCEPTED
input |
---|
2 1 2 1 |
correct output |
---|
2 |
user output |
---|
2 |
Test 4
Verdict: ACCEPTED
input |
---|
500 0 |
correct output |
---|
250 |
user output |
---|
250 |
Test 5
Verdict: ACCEPTED
input |
---|
500 124750 66 104 50 159 173 457 200 154 ... |
correct output |
---|
500 |
user output |
---|
500 |
Test 6
Verdict: ACCEPTED
input |
---|
500 96771 376 390 243 497 417 360 107 80 ... |
correct output |
---|
413 |
user output |
---|
413 |
Test 7
Verdict: ACCEPTED
input |
---|
500 106799 96 245 68 62 122 119 460 454 ... |
correct output |
---|
433 |
user output |
---|
433 |
Test 8
Verdict: ACCEPTED
input |
---|
500 83550 76 338 111 174 88 142 114 463 ... |
correct output |
---|
365 |
user output |
---|
365 |
Test 9
Verdict: ACCEPTED
input |
---|
500 98051 281 60 312 284 270 474 385 224 ... |
correct output |
---|
410 |
user output |
---|
410 |
Test 10
Verdict: ACCEPTED
input |
---|
500 86622 5 320 50 107 182 483 385 500 ... |
correct output |
---|
372 |
user output |
---|
372 |
Test 11
Verdict: ACCEPTED
input |
---|
500 99445 421 286 392 406 155 290 475 453 ... |
correct output |
---|
396 |
user output |
---|
396 |
Test 12
Verdict: ACCEPTED
input |
---|
500 99832 283 149 315 396 264 422 224 388 ... |
correct output |
---|
410 |
user output |
---|
410 |
Test 13
Verdict: ACCEPTED
input |
---|
500 116149 446 185 232 35 498 391 189 63 ... |
correct output |
---|
457 |
user output |
---|
457 |
Test 14
Verdict: ACCEPTED
input |
---|
500 84757 71 205 286 360 184 486 30 228 ... |
correct output |
---|
364 |
user output |
---|
364 |
Test 15
Verdict: ACCEPTED
input |
---|
500 108617 126 250 76 224 449 69 200 63 ... |
correct output |
---|
439 |
user output |
---|
439 |
Test 16
Verdict: ACCEPTED
input |
---|
10 20 7 8 1 3 4 8 5 9 ... |
correct output |
---|
5 |
user output |
---|
5 |
Test 17
Verdict: ACCEPTED
input |
---|
10 20 2 9 9 8 4 3 7 3 ... |
correct output |
---|
5 |
user output |
---|
5 |