Submission #1259561

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259561		user736482	Love Polygon (BOI18_polygon)	C++20	100 / 100	196 ms	10416 KiB

polygon

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000007
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099LL

ll n;
string a,b;
map<string,ll>mp;
ll akk=1;
ll g[100007];
ll dg[100007];
bool uz[100007];
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    ll il=0;
    if(n%2){
        cout<<-1;return 0;
    }
    for(ll i=0;i<n;i++){
        cin>>a>>b;
        if(mp[a]==0)mp[a]=akk++;
        if(mp[b]==0)mp[b]=akk++;
        g[mp[a]]=mp[b];
        if(g[mp[b]]==mp[a] && a!=b){
            il+=2;
            uz[mp[b]]=1;
            uz[mp[a]]=1;
        }
        dg[mp[b]]++;
    }
    
    queue<ll>q;
    for(ll i=1;i<akk;i++){
        if(dg[i]==0)q.push(i);
    }
    while(q.size()){
        ll ak=q.front();
        if(uz[ak])continue;
       // cout<<ak<<" "<<il<<"   ";
        uz[ak]=1;
        q.pop();
        if(uz[g[ak]]){
            continue;
        }
        else{
            il++;
            uz[g[ak]]=1;
            dg[g[g[ak]]]--;
            if(dg[g[g[ak]]]==0)q.push(g[g[ak]]);
        }
    }
   // cout<<il<<" ";
    for(ll i=1;i<akk;i++){
        if(!uz[i]){
            ll cnt=1;
            ll x=g[i];
            uz[i]=1;
            while(x!=i){
                cnt++;
                uz[x]=1;
                x=g[x];
            }
            il+=cnt/2;
        }
    }
    cout<<n-il;
}

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