Submission #314027

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
314027	2020-10-18T00:14:40 Z	sofapuden	Love Polygon (BOI18_polygon)	C++14	50 / 100	405 ms	17888 KB

polygon

#include <bits/stdc++.h>

using namespace std;

int main(){
	int n, ans = 0; cin >> n;
	vector<pair<string,string>> in;
	vector<int> belove(n), love(n);
	
	map<string,int> M;
	
	queue<int> nobody;
	
	vector<bool> vis(n,false);
	
	if(n & 1){
		cout << "-1\n"; return 0;
	}
	
	for(int i = 0; i < n; ++i){
		string s1, s2; cin >> s1 >> s2;
		M[s1] = i;
		in.push_back({s1,s2});
	}
	for(int i = 0; i < n; ++i){
		love[M[in[i].first]] = M[in[i].second];
		belove[M[in[i].second]]++;
	}
	for(int i = 0; i < n; ++i){
		if(love[love[i]] == i && love[i] != i)vis[i] = true;
		if(!belove[i]){nobody.push(i);}
	}
	while(!nobody.empty()){
		auto x = nobody.front();
		nobody.pop();
		vis[x] = true;
		if(!vis[love[x]]){
			vis[love[x]] = true;
			if(--belove[love[love[x]]] == 0)nobody.push(love[love[x]]);
		}
		ans++;
	}
	for(int i = 0; i < n; ++i){
		if(!vis[i]){
			vis[i] = true;
			int last = i;
			vis[last] = true;
			int cnt = 2;
			while(love[last] != i){
				cnt++;
				last = love[last];
				vis[last] = true;
			}
			ans+=(cnt+1)>>1;
		}
	}
	cout << ans << "\n";
}

Subtask #1

21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	256 KB	Output is correct
3	Correct	1 ms	256 KB	Output is correct
4	Correct	0 ms	256 KB	Output is correct
5	Correct	1 ms	256 KB	Output is correct
6	Correct	0 ms	256 KB	Output is correct
7	Correct	1 ms	256 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	1 ms	256 KB	Output is correct
11	Correct	0 ms	384 KB	Output is correct
12	Correct	1 ms	256 KB	Output is correct
13	Correct	1 ms	256 KB	Output is correct
14	Correct	1 ms	256 KB	Output is correct
15	Correct	0 ms	256 KB	Output is correct

Subtask #2

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Incorrect	0 ms	256 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #3

29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	383 ms	15516 KB	Output is correct
2	Correct	380 ms	17468 KB	Output is correct
3	Correct	342 ms	17492 KB	Output is correct
4	Correct	1 ms	1152 KB	Output is correct
5	Correct	380 ms	17568 KB	Output is correct
6	Correct	381 ms	17620 KB	Output is correct
7	Correct	405 ms	17620 KB	Output is correct
8	Correct	364 ms	17492 KB	Output is correct
9	Correct	370 ms	17876 KB	Output is correct
10	Correct	320 ms	17888 KB	Output is correct
11	Correct	1 ms	256 KB	Output is correct
12	Correct	0 ms	256 KB	Output is correct
13	Correct	1 ms	256 KB	Output is correct
14	Correct	1 ms	256 KB	Output is correct

Subtask #4

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	256 KB	Output is correct
3	Correct	1 ms	256 KB	Output is correct
4	Correct	0 ms	256 KB	Output is correct
5	Correct	1 ms	256 KB	Output is correct
6	Correct	0 ms	256 KB	Output is correct
7	Correct	1 ms	256 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	1 ms	256 KB	Output is correct
11	Correct	0 ms	384 KB	Output is correct
12	Correct	1 ms	256 KB	Output is correct
13	Correct	1 ms	256 KB	Output is correct
14	Correct	1 ms	256 KB	Output is correct
15	Correct	0 ms	256 KB	Output is correct
16	Correct	1 ms	256 KB	Output is correct
17	Correct	0 ms	256 KB	Output is correct
18	Incorrect	0 ms	256 KB	Output isn't correct
19	Halted	0 ms	0 KB	-