Submission #1259828

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259828		M_W_13	Love Polygon (BOI18_polygon)	C++20	100 / 100	192 ms	23520 KiB

polygon

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define st first
#define nd second
#define pb push_back
map<string, int> m;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    if (n % 2 == 1) {
        cout << -1 << '\n';
        return 0;
    }
    vector<pair<string, string>> vec;
    set<string> S;
    rep(i, n) {
        string a, b;
        cin >> a >> b;
        vec.pb({a, b});
        S.insert(a);
        S.insert(b);
    }
    int kt = 1;
    for (auto s: S) {
        m[s] = kt;
        kt++;
    }
    int dokad[n + 1];
    dokad[0] = 0;
    rep(i, n) {
        dokad[m[vec[i].st]] = m[vec[i].nd];
    }
    bool uzyte[n + 1];
    rep(i, n + 1) {
        uzyte[i] = false;
    }
    for (int v = 1; v <= n; v++) {
        int w = dokad[v];
        if (uzyte[w]) {
            dokad[v] = v;
            continue;
        }
        if (w != v && dokad[w] == v) {
            uzyte[v] = true;
            uzyte[w] = true;
        }
    }
    int ans = 0;
    int ile[n + 1];
    rep(i, n + 1) {
        ile[i] = 0;
    }
    for (int v = 1; v <= n; v++) {
        int w = dokad[v];
        if (uzyte[w]) {
            dokad[v] = v;
        }
        if (dokad[v] != v) {
            ile[dokad[v]]++;
        }
    }
    queue<int> q;
    for (int v = 1; v <= n; v++) {
        if (uzyte[v]) continue;
        if (ile[v] == 0) {
            q.push(v);
        }
    }
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        if (uzyte[v]) continue;
        int w = dokad[v];
        if (uzyte[w] || w == v) {
            ans++;
            uzyte[v] = true;
        }
        else {
            uzyte[v] = true;
            uzyte[w] = true;
            ans++;
            int z = dokad[w];
            ile[z]--;
            if (!uzyte[z] && ile[z] == 0) {
                q.push(z);
            }
        }
    }
    for (int v = 1; v <= n; v++) {
        if (uzyte[v]) continue;
        int w = v;
        int s = 0;
        while (!uzyte[w]) {
            uzyte[w] = true;
            w = dokad[w];
            s++;
        }
        ans += (s/2);
        ans += (s % 2);
    }
    cout << ans << '\n';
    return 0;
}

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