제출 #718168

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
718168		amirhoseinfar1385	Love Polygon (BOI18_polygon)	C++17	29 / 100	283 ms	27620 KiB

polygon

#include<bits/stdc++.h>
using namespace std;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	map<string,int>mp;
	vector<int>cnt(n+1);
	vector<vector<int>>revadj(n+1);
	vector<pair<string,string>>all(n);
	for(int i=0;i<n;i++){
		cin>>all[i].first>>all[i].second;
		mp[all[i].first]=i;
	}
	vector<int>adj(n+1);
	for(int i=0;i<n;i++){
		int x=mp[all[i].second];
		revadj[x].push_back(i);
		adj[i]=x;
		cnt[x]++;
	}
	if(n&1){
		cout<<-1<<"\n";
		return 0;
	}
	int res=n;
	set<pair<int,int>>st;
	for(int i=0;i<n;i++){
		st.insert(make_pair(cnt[i],i));
	}
	while((int)st.size()>0){
		auto x=*st.begin();
		st.erase(x);
		//cout<<x.second<<" "<<adj[x.second]<<'\n';
		if(adj[x.second]==x.second){
			continue;
		}
		res--;
		for(auto y:revadj[x.second]){
			st.erase(make_pair(cnt[y],y));
		}
	//	cout<<x.second<<'\n';
		st.erase(make_pair(cnt[adj[x.second]],adj[x.second]));
		if(st.count(make_pair(cnt[adj[adj[x.second]]],adj[adj[x.second]]))==1){
			st.erase(make_pair(cnt[adj[adj[x.second]]],adj[adj[x.second]]));
			cnt[adj[adj[x.second]]]--;
			st.insert(make_pair(cnt[adj[adj[x.second]]],adj[adj[x.second]]));
		}		
		for(auto y:revadj[adj[x.second]]){
			st.erase(make_pair(cnt[y],y));
		}
	}
	cout<<res<<'\n';
}

• Subtask 1: 0 / 21
• Subtask 2: 0 / 25
• Subtask 3: 29 / 29
• Subtask 4: 0 / 25