oj.uz

Submission #314024

# Submission time Handle Problem Language Result Execution time Memory
314024 2020-10-17T23:59:52 Z sofapuden Love Polygon (BOI18_polygon) C++14
0 / 100
 564 ms 27512 KB 
#include <bits/stdc++.h>

using namespace std;

int main(){
	int n, ans = 0; cin >> n;
	vector<pair<string,string>> in;
	vector<vector<int>> belove(n);
	vector<int> love(n);
	vector<int> cn(n);
	
	map<string,int> M;
	set<int> iR;
	
	queue<int> nobody;
	queue<int> sad;
	
	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];
		if(in[i].first != in[i].second)belove[M[in[i].second]].push_back(M[in[i].first]);
	}
	for(int i = 0; i < n; ++i){
		if(love[love[i]] == i && love[i] != i)iR.insert(i);
		if(love[i] == i){iR.insert(i);ans++;}
		cn[i] = belove[i].size();
		if(cn[i] == 0)sad.push(i);
	}
	for(int i = 0; i < n; ++i){
		if(love[i] == i || (iR.count(love[i]) && !iR.count(i)))nobody.push(i);
	}
	while(!nobody.empty() || !sad.empty()){
		while(!nobody.empty()){
			auto x = nobody.front();
			nobody.pop();
			if(iR.count(x))continue;
			if(belove[x].size()){
				iR.insert(x);
				iR.insert(belove[x][0]);
				cout << x << " " << belove[x][0] << "\n";
				ans++;
				for(int i = 0; i < (int)belove[x].size(); ++i){
					if(!iR.count(belove[x][i]))nobody.push(belove[x][i]);
				}
			}
		}
		if(!sad.empty()){
			auto x = sad.front();
			sad.pop();
			if(iR.count(x)){continue;}
			if(iR.count(love[x])){ans++; iR.insert(x); continue;}
			iR.insert(x);
			iR.insert(love[x]);
			cout << x << " " << love[x] << "\n";
			ans++;
			for(int i = 0; i < (int)belove[love[x]].size(); ++i){
				if(!iR.count(belove[love[x]][i]))nobody.push(belove[love[x]][i]);
			}
			cn[love[love[x]]]--;
			if(!cn[love[love[x]]]){
				sad.push(love[love[x]]);
			}
		}
	}
	for(int i = 0; i < n; ++i){
		if(!vis[i] && !iR.count(i)){
			int last = i;
			vis[last] = true;
			int cnt = 2;
			while(love[last] != i){
				cout << i << "\n";
				cnt++;
				last = love[last];
				vis[last] = true;
			}
			ans+=(cnt+1)>>1;
		}
	}
	cout << ans << "\n";
}

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

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

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 564 ms 27512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -