Submission #718179

#	Time	Username	Problem	Language	Result	Execution time	Memory
718179		amirhoseinfar1385	Love Polygon (BOI18_polygon)	C++17	100 / 100	297 ms	28380 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;
    	vector<int>visa(n+1);
    	for(int i=0;i<n;i++){
    		if(adj[i]!=i&&adj[adj[i]]==i){
    			res--;
    			visa[i]=1;
    			continue;
    		}
    		st.insert(make_pair(cnt[i],i));
    	}
    	while((int)st.size()>0){
    		auto x=*st.begin();
    		if(x.first>=1){
    			vector<int>vis(n+2);
    			for(int i=0;i<n;i++){
    				if(st.count(make_pair(cnt[i],i))==0){
    					vis[i]=1;
    				}
    			}
    			for(int i=0;i<n;i++){
    				if(vis[i]==0){
    					int cnta=0;
    					int fi=i;
    					while(vis[fi]==0){
    						vis[fi]=1;
    						cnta++;
    					//	cout<<fi<<" "<<adj[fi]<<'\n';
    						fi=adj[fi];
    					}
    					if(cnta==2){
    						res-=cnta;
    						continue;
    					}
    					//cout<<i<<" "<<cnt<<"\n";
    					res-=(cnta)/2;
    				}
    			}
    			break;
    		}
    		st.erase(x);
    		//cout<<x.second<<" "<<adj[x.second]<<'\n';
    		if(adj[x.second]==x.second||visa[adj[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: 21 / 21
• Subtask 2: 25 / 25
• Subtask 3: 29 / 29
• Subtask 4: 25 / 25