Submission #951573

#	Time	Username	Problem	Language	Result	Execution time	Memory
951573		SaMuEl0516	Love Polygon (BOI18_polygon)	C++17	0 / 100	146 ms	33568 KiB

polygon

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
gp_hash_table<string,int>ht;
vector<int>cnt[(int)1e5+5];
int out[(int)1e5+5],sz[(int)1e5+5];
bool vis[(int)1e5+5];
set<pair<int,int>>se;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,c=0,u,v,ans=0;
    string s,t;
    cin>>n;
    if(n%2){
        cout<<-1;
        return 0;
    }
    for(int i=0;i<n;i++){
        cin>>s>>t;
        if(ht.find(s)!=ht.end())u=ht[s];
        else u=ht[s]=c++;
        if(ht.find(t)!=ht.end())v=ht[t];
        else v=ht[t]=c++;
        out[u]=v;
        if(u==v)continue;
        cnt[u].push_back(v),cnt[v].push_back(u);
        sz[u]++,sz[v]++;
    }
    for(auto p:ht)cout<<p.first<<' '<<p.second<<'\n';
    for(int i=0;i<n;i++){
        if(out[out[i]]==i&&out[i]!=i&&!vis[i]){
            ans+=2,vis[i]=vis[out[i]]=1;
            for(int j:cnt[i])sz[j]--;
        }
    }
    for(int i=0;i<n;i++)se.insert({sz[i],i});
    while(se.size()){
        auto p=*se.begin();
        se.erase(se.begin());
        if(p.first==0||vis[p.second])continue;
        for(int i:cnt[p.second]){
            if(!vis[i]){
                vis[p.second]=vis[i]=1;
                for(int j:cnt[p.second]){
                    if(!vis[j]){
                        se.erase({sz[j],j});
                        sz[j]--;
                        se.insert({sz[j],j});
                    }
                }
                for(int j:cnt[i]){
                    if(!vis[j]){
                        se.erase({sz[j],j});
                        sz[j]--;
                        se.insert({sz[j],j});
                    }
                }
                ans++;
                break;
            }
        }
    }
    cout<<n-ans;
}

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