Submission #1090128

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090128		andrei_iorgulescu	Love Polygon (BOI18_polygon)	C++14	100 / 100	192 ms	16532 KiB

polygon

#include <bits/stdc++.h>

using namespace std;

int n;
int bruvv;
map<string, int> nume;
int f[100005];
int indeg[100005];
bool taken[100005];
bool viz[100005];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        string x, y;
        cin >> x >> y;
        if (nume[x] == 0)
            nume[x] = ++bruvv;
        if (nume[y] == 0)
            nume[y] = ++bruvv;
        int xx = nume[x], yy = nume[y];
        f[xx] = yy;
    }
    if (n % 2 == 1)
    {
        cout << -1;
        return 0;
    }
    set<pair<int,int>> s;
    int op = n;
    for (int i = 1; i <= n; i++)
    {
        if (f[i] != i and f[f[i]] == i)
            op--, taken[i] = true;
        else
            indeg[f[i]]++;
    }
    for (int i = 1; i <= n; i++)
    {
        if (f[i] == i or f[f[i]] != i)
            s.insert({indeg[i], i});
    }
    bool wow = false;
    while (!s.empty())
    {
        pair<int,int> pr = *s.begin();
        s.erase(pr);
        int x = pr.second;
        if (indeg[x] != 0)
        {
            wow = true;
            break;
        }
        if (!taken[f[x]])
        {
            taken[x] = true;
            taken[f[x]] = true;
            op--;
            s.erase({indeg[f[x]], f[x]});
            if (!taken[f[f[x]]])
            {
                s.erase({indeg[f[f[x]]], f[f[x]]});
                indeg[f[f[x]]]--;
                s.insert({indeg[f[f[x]]], f[f[x]]});
            }
        }
        else
            f[x] = x;
    }
    if (wow)
    {
        vector<int> noduri_lmao;
        for (int i = 1; i <= n; i++)
            if (!taken[i])
                noduri_lmao.push_back(i);
        for (auto it : noduri_lmao)
        {
            if (!viz[it])
            {
                int sz = 0;
                int xx = it;
                while (!viz[xx])
                {
                    viz[xx] = true;
                    sz++;
                    xx = f[xx];
                }
                op -= (sz - (sz / 2 + sz % 2));
            }
        }
    }
    cout << op;
    return 0;
}

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