제출 #1280273

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1280273		Newtonabc	Love Polygon (BOI18_polygon)	C++20	100 / 100	239 ms	15588 KiB

polygon

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
map<string,int> mp;
pair<string,string> arr[N];
int p[N],indeg[N];
bool out[N];
int main(){
    int n,ans;
    cin>>n;
    ans=n;
    for(int i=1;i<=n;i++){
        cin>>arr[i].first >>arr[i].second;
    }
    if(n%2==1){
        cout<<-1;
        return 0;
    }
    for(int i=1;i<=n;i++) mp[arr[i].first]=i;
    for(int i=1;i<=n;i++){
        p[i]=mp[arr[i].second];
    }
    for(int i=1;i<=n;i++) indeg[p[i]]++;
    for(int i=1;i<=n;i++){
        if(out[i]) continue;
        if(p[p[i]]==i && p[i]!=i){
            out[i]=true,out[p[i]]=true,ans-=2;
        }
    }
    //for(int i=1;i<=n;i++) cout<<i <<" " <<p[i] <<"\n";
    queue<int> q;
    for(int i=1;i<=n;i++) if(indeg[i]==0) q.push(i);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        if(out[u] || out[p[u]]) continue;
        ans--;
        indeg[p[p[u]]]--;
        out[u]=out[p[u]]=true;
        if(indeg[p[p[u]]]==0) q.push(p[p[u]]);
    }
    //cout<<ans <<"\n";
    for(int i=1;i<=n;i++) if(out[i]==false && out[p[i]]==true) out[i]=true;
    for(int i=1;i<=n;i++){
        if(out[i] || p[i]==i) continue;
        int u=p[i],cnt=1;
        //cout<<i <<"\n";
        while(u!=i){
            cnt++;
            out[u]=true;
            u=p[u];
        }
        //cout<<"\n";
        ans-=cnt/2;
    }
    cout<<ans;
}

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