Submission #1194373

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194373		teletubigam3	Love Polygon (BOI18_polygon)	C++20	100 / 100	189 ms	14200 KiB

polygon

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#define se second
#define pb push_back
#define fi first
#define fo(var, n) for(long long var=0;var<n;var++)
#define fore(var, n) for(long long var=n-1;var>=0;var--)
using namespace std;
using ll = long long;


int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);

    int tt = 1;
    //cin>>tt;

    while(tt--)
    {
        int n; cin>>n;
        map<string, int> t;
        int jj=0;
        int cnt[n];
        fo(i,n) cnt[i] = 0;
        int tar[n];
        fo(i,n)
        {
            string a, b; cin>>a>>b;
            if(t.find(a) == t.end()) {t[a] = jj;jj++;}
            if(t.find(b) == t.end()) {t[b] = jj;jj++;}
            cnt[t[b]]++;
            tar[t[a]] = t[b];
            if(a == b) cnt[t[b]]--;
        }
        if(n&1)
        {
            cout<<"-1\n"; continue;
        }
        set<pair<int,int>> c;
        fo(i,n) c.insert({cnt[i], i});
        int ans=0, sad=0;
        int hav[n];
        fo(i,n) hav[i] = 0;
       // fo(i,n) cout<<tar[i]<<" ";cout<<"\n";
        fo(i, n) if(tar[i] != i && tar[tar[i]] == i){hav[i]=1; hav[tar[i]] = 1;}
        fo(i,n)
        {
            auto x = c.begin();
            int j = (*x).se;
            c.erase(x);
            //cout<<j<<" "<<cnt[j]<<" "<<ans<<"\n";
            if(hav[j]) continue;
            if(hav[tar[j]] || tar[j] == j)
            {
                ans++; hav[j]=1;
            }
            else
            {
                ans++; hav[j]=1; hav[tar[j]]=1;
                if(c.count({cnt[tar[tar[j]]], tar[tar[j]]}))
                {
                    c.erase({cnt[tar[tar[j]]], tar[tar[j]]});
                    cnt[tar[tar[j]]]--;
                    c.insert({cnt[tar[tar[j]]], tar[tar[j]]});
                }
            }
        }
        cout<<ans<<"\n";
    }



    return 0;
}

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