Submission #1218359

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218359		Malix	Love Polygon (BOI18_polygon)	C++20	100 / 100	203 ms	13452 KiB

polygon

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
#define all(x) x.begin(),x.end()
 
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;
 
int n;
map<string,int> mp;
vi a,arr,vis;
 
void dfs(int x){
    arr.PB(x);
    vis[x]=1;
    if(!vis[a[x]])dfs(a[x]);
}

int main() {
// ios::sync_with_stdio(0);
// cin.tie(0);
// freopen("test_input.txt", "r", stdin);
// freopen("test_output.txt", "w", stdout);
    cin>>n;
    a.resize(n);vis.resize(n,0);
    int tmp=1;
    vi ord,deg(n,0);
    REP(i,0,n){
        string x,y;cin>>x>>y;
        if(mp[x]==0)mp[x]=tmp++;
        if(mp[y]==0)mp[y]=tmp++;
        a[mp[x]-1]=mp[y]-1;
        if(mp[x]!=mp[y])deg[mp[y]-1]++;
        // cout<<mp[x]-1<<" "<<mp[y]-1<<"\n";
    }
    if(n%2){
        cout<<-1;
        return 0;
    }
    REP(i,0,n)if(a[i]!=i&&a[i]!=-1&&i==a[a[i]]){
        a[a[i]]=-1;
        a[i]=-1;
    }
    REP(i,0,n)if(a[i]!=-1&&a[a[i]]==-1)a[i]=i;
    queue<int> q;
    REP(i,0,n)if(deg[i]==0&&a[i]!=-1){
        q.push(i);
        ord.PB(i);
    }
    while(!q.empty()){
        int x=q.front();
        deg[a[x]]--;
        if(deg[a[x]]==0){
            q.push(a[x]);
            ord.PB(a[x]);
        }
        q.pop();
    }
    int ans=0;
    int sz=ord.size();
    vi ord2;
    REP(i,0,sz)if(!vis[ord[i]]){
        ans++;
        vis[a[ord[i]]]=1;
        vis[ord[i]]=1;
        deg[a[ord[i]]]--;
        if(deg[a[ord[i]]]==0)ord2.PB(a[a[ord[i]]]);
    }
    sz=ord2.size();
    REP(i,0,sz)if(vis[ord2[i]]==0&&a[ord2[i]]!=-1){
        dfs(ord2[i]);
        int k=arr.size();
        ans+=k/2+k%2;
        arr.clear();
    }
    REP(i,0,n)if(vis[i]==0&&a[i]!=-1){
        dfs(i);
        int k=arr.size();
        ans+=k/2+k%2;
        arr.clear();
    }
    cout<<ans;
}

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