Submission #1259506

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259506		Szymon_Pilipczuk	Love Polygon (BOI18_polygon)	C++20	54 / 100	67 ms	15292 KiB

polygon

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(),a.end()
#define rep(a,b) for(int a = 0;a<b;a++)
const int inf = 1e9;
const ll infl = 1e18;
bool used[100000];
int nx[100000];
int c[100000];
unordered_map<string,int> conv;
queue<int> q;
int ans = 0;
int main()
{
    int n;
    cin>>n;
    vector<pair<string,string>> a(n);
    rep(i,n)
    {
        cin>>a[i].st>>a[i].nd;
        conv[a[i].st] = i;
    }
    if(n%2 == 1)
    {
        cout<<-1;
        return 0;
    }
    rep(i,n)
    {
        nx[i] = conv[a[i].nd];
        c[nx[i]]++;
    }
    rep(i,n)
    {
        if(c[i] == 0)
        {
            q.push(i);
        }
    }
    while(!q.empty())
    {
        int cc = q.front();
        q.pop();
        if(used[nx[cc]])
        {
            ans++;
            used[cc] = true;
        }
        else
        {
            ans++;
            used[cc] = true;
            used[nx[cc]] = true;
            c[nx[nx[cc]]]--;
            if(c[nx[nx[cc]]] == 0 && !used[nx[nx[cc]]])
            {
                q.push(nx[nx[cc]]);
            }
        }
    }
    rep(i,n)
    {
        if(!used[i])
        {
            used[i] = true;
            int c = 1;
            int cc = nx[i];
            while(cc != i)
            {
                used[cc] = true;
                c++;
                cc = nx[cc];
            }
            if(c != 2)ans += (c+1)/2;
        }
    }
    cout<<ans;


}

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