Submission #895698

#	Time	Username	Problem	Language	Result	Execution time	Memory
895698		krizsu222	Love Polygon (BOI18_polygon)	C++17	0 / 100	197 ms	20308 KiB

polygon

#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 1e5+2;

int n, out[maxn], actnr, ilpoj, res;
string name1, name2;
set <int> in[maxn];
map <string, int> nr;
queue <int> q;
bool done[maxn];

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

    cin >> n;
    
    for(int i=1; i<=n; i++)
    {
        cin >> name1 >> name2;
        if(!nr[name1]) nr[name1] = ++actnr;
        // cout << name1 << ": " << nr[name1] << '\n';
        if(!nr[name2]) nr[name2] = ++actnr;
        // cout << name2 << ": " << nr[name2] << '\n';
        out[nr[name1]] = nr[name2];
        in[nr[name2]].insert(nr[name1]);
    }

    if(n&1)
    {
        cout << "-1\n";
        return 0;
    }

    for(int i=1; i<=n; i++)
    {
        if(out[i] == i) ilpoj++, done[i] = 1;
        else if(out[out[i]] == i) done[i] = done[out[i]] = 1;
        else if(!in[i].size()) q.push(i);
    }

    while(!q.empty())
    {
        int v = q.front(); q.pop();
        if(done[out[v]]) ilpoj++, done[v] = 1;
        else
        {
            int u = out[v];
            in[out[u]].erase(u);
            if(!in[out[u]].size()) q.push(out[u]);
            done[v] = done[u] = 1; res++;
        }
    }

    for(int i=1; i<=n; i++)
    {
        if(done[i]) continue;
        int v = i, act = 0;
        while(out[v] != i) act++, v = out[v];
        ilpoj += (act&1); res += (act/2);
    }

    cout << res+ilpoj << '\n';
}

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