Submission #388415

#	Time	Username	Problem	Language	Result	Execution time	Memory
388415		leaked	Love Polygon (BOI18_polygon)	C++14	100 / 100	401 ms	24140 KiB

polygon

#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define vec vector
#define pb push_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define f first
#define s second
using namespace std;
typedef unsigned long long ull;
auto rnd=bind(uniform_int_distribution<long long>(1,1e18),mt19937(time(0)));
int getans(int x){
    if(x==2){
        return 2;
    }
    return x/2;
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    map<string,int>mp;
    vec<string>obrr;
    int cr=0;
    vec<int>con(n,0);
    vec<set<int>>obr(n,set<int>());
    for(int i=0;i<n;i++){
        string a,b;
        cin>>a>>b;
        if(!mp.count(a)) mp[a]=cr++,obrr.pb(a);
        if(!mp.count(b)) mp[b]=cr++,obrr.pb(b);
        con[mp[a]]=mp[b];
        obr[mp[b]].insert(mp[a]);
    }
    if(n%2){
        cout<<-1;
        return 0;
    }
    assert(cr==n);
    int ans=0;
    queue<int>q;
    vec<bool>inq(n,0);
    for(int i=0;i<n;i++){
        if(!sz(obr[i]) ) q.push(i),inq[i]=1;
    }
    vec<bool>used(n,0);
    vec<int>is(n,0);/// did i used my edge i->u
    /// #WARNING WITH CYCLES OF LENGTH 2
    for(int i=0;i<n;i++){
        if(i!=con[i] && con[con[i]]==i){
            is[i]=1;
            is[con[i]]=1;
            used[i]=1;
        }
    }
    while(!q.empty()){
        int v=q.front();q.pop();
//        cerr<<obrr[v]<<endl;
        if(!used[v] && !used[con[v]]){
            used[v]=1;
            used[con[v]]=1;
            int u=con[v];
            obr[con[u]].erase(u);
            is[v]=1;
            if(!sz(obr[con[u]]) && !inq[con[u]]) inq[con[u]]=1,q.push(con[u]);
        }
        else if(!used[con[v]]){
            obr[con[v]].erase(v);
            if(!sz(obr[con[v]]) && !inq[con[v]]) inq[con[v]]=1,q.push(con[v]);
        }
    }
    for(int i=0;i<n;i++){
        if(used[i]) continue;
        int v=i;
        int cyc=0;
        while(1){
            cyc++;
            if(cyc%2==0) is[v]=1;
            used[v]=1;
            v=con[v];
            if(used[v]) break;
        }
    }
//    for(int i=0;i<n;i++){
//        cerr<<obrr[i]<<' '<<obrr[con[i]]<<' '<<is[i]<<endl;
//    }
    for(auto &z : is) ans+=1-z;
    cout<<ans;
    return 0;
}

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