Submission #1089927

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089927		gyg	Love Polygon (BOI18_polygon)	C++17	100 / 100	143 ms	23604 KiB

polygon

#include <bits/stdc++.h>
using namespace std;
#define arr array
#define vct vector
#define hmap unordered_map
#define str string
#define pii pair<int, int>
#define hset unordered_set
const int MX_N = 1e5 + 5;

int n;
arr<int, MX_N> ot;

arr<int, MX_N> in_cnt;
arr<bool, MX_N> dltd;
set<pii> ord; // {in_cnt[u], u}
void intls() {
    for (int u = 1; u <= n; u++) in_cnt[ot[u]]++;
    for (int u = 1; u <= n; u++) ord.insert({in_cnt[u], u});
}
void dlt(int u) {
    dltd[u] = true;
    ord.erase({in_cnt[u], u});
    if (dltd[ot[u]]) return;
    ord.erase({in_cnt[ot[u]], ot[u]});
    in_cnt[ot[u]]--;
    ord.insert({in_cnt[ot[u]], ot[u]});
}

int prcmp() {
    int ans = 0;
    for (int u = 1; u <= n; u++) {
        if (dltd[u]) continue;
        if (ot[u] == u) continue;
        if (ot[ot[u]] != u) continue;
        ans += 2;
        dlt(u), dlt(ot[u]);
    }
    return ans;
}

int grdy() {
    int ans = 0;
    while (ord.size()) {
        int u = ord.begin()->second;
        if (ot[u] == u || dltd[ot[u]]) { dlt(u); continue; }
        ans++;
        dlt(u), dlt(ot[u]);
    }
    return ans;
}

int main() {
    // freopen("lv.in", "r", stdin);
    cin >> n;
    hmap<int, str> ot_str;
    hmap<str, int> ind;
    for (int u = 1; u <= n; u++) {
        str x, y; cin >> x >> y;
        ind[x] = u, ot_str[u] = y;
    }
    for (int u = 1; u <= n; u++) ot[u] = ind[ot_str[u]];

    if (n % 2 == 1) { cout << -1 << endl; exit(0); }
    intls();
    int ans = prcmp() + grdy();
    cout << n - ans << endl;
}

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