Submission #1194348

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194348		teletubigam3	Love Polygon (BOI18_polygon)	C++20	0 / 100	155 ms	10164 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++;
            if(t.find(b) == t.end()) t[b] = jj++;
            cnt[t[b]]++;
            tar[t[a]] = t[b];
            if(a == b) cnt[t[b]]--;
        }
        if(n&1)
        {
            cout<<"-1\n"; continue;
        }
        pair<int,int> c[n];
        fo(i,n) c[i] = {cnt[i], i};
        sort(c,c+n);
        int ans=0, sad=0;
        int hav[n];
        fo(i,n) hav[i] = 0;
        //fo(i,n) cout<<cnt[i]<<" ";cout<<"\n";
        fo(i, n) if(tar[i] != i && tar[tar[i]] == i){hav[i]=1; hav[tar[i]] = 1;}
        fo(i,n)
        {
            int j = c[i].se;
            if(hav[j]) continue;
            if(hav[tar[j]] || tar[j] == j)
            {
                ans++; hav[j]=1;
            }
            else
            {
                ans++; hav[j]=1; hav[tar[j]]=1;
            }
            //cout<<j<<" "<<ans<<"\n";
        }
        cout<<ans<<"\n";
    }



    return 0;
}

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