Submission #1005662

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005662		LonlyR	Love Polygon (BOI18_polygon)	C++17	100 / 100	211 ms	16496 KiB

polygon

#include<bits/stdc++.h>
#define int long long

using namespace std;
const int maxn = 1e5 + 5;
int n, ans;
map<string,int> mp;
set<int> s;
queue<int> q;
int deg[maxn], nxt[maxn], nxt_two[maxn], mark[maxn];

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        string u, v;
        cin >> u >> v;
        if (!mp.count(u)) mp[u] = mp.size() + 1;
        if (!mp.count(v)) mp[v] = mp.size() + 1;
        nxt[mp[u]] = mp[v];
        deg[mp[v]]++;
    }
    if (mp.size() & 1) return cout << -1, 0;
    n = mp.size();
    for (int i = 1; i <= n; i++)
        nxt_two[i] = nxt[nxt[i]],
        s.emplace(i),
        mark[i] = 1;
    int cnt = n;
    for (int i = 1; i <= n; i++)
        if (mark[i] && nxt_two[i] == i && nxt[i] != i)
        {
            mark[i] = mark[nxt[i]] = 0;
            s.erase(i); s.erase(nxt[i]);
            cnt -= 2;
        }
    for (int i = 1; i <= n; i++)
        if (mark[i] && deg[i] == 0)
            q.emplace(i);
    while (cnt)
    {
        if (q.empty()) q.emplace(*s.begin());
        int u = q.front();
        q.pop();
        mark[u] = 0;
        s.erase(u);
        ans++;
        cnt--;
        if (mark[nxt[u]])
        {
            s.erase(nxt[u]);
            cnt--;
            mark[nxt[u]] = 0;
            deg[nxt_two[u]]--;
            if (mark[nxt_two[u]] && deg[nxt_two[u]] == 0)
                q.emplace(nxt_two[u]);
        } 
    }
    cout << ans;
}

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