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