Submission #1272214

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272214		yehudalester	Love Polygon (BOI18_polygon)	C++20	100 / 100	364 ms	38500 KiB

polygon

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
vector<ll> nxt(1e6,-1);
map<string,ll> mp;
map<string,string> nx;
int main(){
    ll n;cin>>n;
    if(n%2){cout << -1;return 0;}
    for(int i=0;i<n;i++){
        string a,b;cin>>a>>b;
        mp[a]=i;
        nx[a]=b;
    }
    vector<ll> indeg(n);
    for(pair<string,string> p:nx){
        nxt[mp[p.first]]=mp[p.second];
        indeg[mp[p.second]]++;
    }
    vector<set<ll>> in(n+1);
    vector<ll> taken(n);
    for(ll i=0;i<n;i++){
        if(nxt[nxt[i]]==i&&nxt[i]!=i)taken[i]=1;
        else in[indeg[i]].insert(i);
    }
    vector<ll> alone;
    ll res=0;
    while(1){
        if(in[0].size()==0){
            if(in[1].size()==0)break;
            else{
                int i=*in[1].begin();
                in[1].erase(i);
                if(nxt[i]==i){alone.push_back(i);}
                else{
                in[1].erase(nxt[i]);
                taken[i]=taken[nxt[i]]=1;
                if(!taken[nxt[nxt[i]]]){
                in[1].erase(nxt[nxt[i]]);
                in[0].insert(nxt[nxt[i]]);
                }
                res++;}
            }
        }
        else{
            int i=*in[0].begin();
            in[0].erase(i);
            if(nxt[i]==i){alone.push_back(i);}
            else{
            if(taken[nxt[i]])alone.push_back(i);
            else{
                res++;
                in[indeg[nxt[i]]].erase(nxt[i]);
                taken[nxt[i]]=1;taken[i]=1;
                if(!taken[nxt[nxt[i]]]){
                in[indeg[nxt[nxt[i]]]].erase(nxt[nxt[i]]);
                indeg[nxt[nxt[i]]]--;
                in[indeg[nxt[nxt[i]]]].insert(nxt[nxt[i]]);
                }
            }
            }
        }
    }
    cout << res+alone.size();
    return 0;
}

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