CSES - HIIT Open 2017 - Results
Submission details
Task:Factory
Sender:Game of Nolife
Submission time:2017-05-27 12:41:22 +0300
Language:C++
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.06 sdetails
#2ACCEPTED0.04 sdetails
#3ACCEPTED0.06 sdetails
#4ACCEPTED0.13 sdetails
#5ACCEPTED0.16 sdetails
#6ACCEPTED0.12 sdetails
#7ACCEPTED0.14 sdetails
#8ACCEPTED0.10 sdetails
#9ACCEPTED0.12 sdetails
#10ACCEPTED0.10 sdetails
#11ACCEPTED0.14 sdetails
#12ACCEPTED0.14 sdetails
#13ACCEPTED0.16 sdetails
#14ACCEPTED0.12 sdetails
#15ACCEPTED0.12 sdetails
#16ACCEPTED0.05 sdetails
#17ACCEPTED0.04 sdetails

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