Submission #862376

#	Time	Username	Problem	Language	Result	Execution time	Memory
862376		The_Samurai	Love Polygon (BOI18_polygon)	C++17	54 / 100	254 ms	22352 KiB

polygon

#include "bits/stdc++.h"

using namespace std;
using ll = long long;
const int inf = 1e9;

int main() {
    cin.tie(0)->sync_with_stdio(false);
#ifdef sunnatov
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int n, z = 0;
    cin >> n;
    if (n % 2) {
        cout << -1;
        return 0;
    }
    vector<pair<string, string>> adj(n);
    for (auto &it: adj) cin >> it.first >> it.second;
    map<string, int> mp;
    for (auto &it: adj) mp[it.first];
    for (auto &it: adj) mp[it.second];
    for (auto &it: mp) it.second = z++;
    set<pair<int, int>> st;
    vector<int> out(n), in(n);
    for (int i = 0; i < n; i++) out[mp[adj[i].first]] = mp[adj[i].second];
//    for (int i = 0; i < n; i++) cout << mp[adj[i].first] << ' ' << mp[adj[i].second] << endl;
    for (int i = 0; i < n; i++) in[out[i]]++;
//    for (int i = 0; i < n; i++) cout << in[i] << ' ';
//    cout << endl;
    for (int i = 0; i < n; i++) st.insert(make_pair(in[i], i));
    vector<bool> changed(n);
    int ans = 0;
    while (!st.empty()) {
        auto [c, u] = *st.begin(); st.erase(st.begin());
        if (u == out[u] or changed[out[u]]) continue;
        int v = out[u];
        if (u != out[v]) {
            st.erase(make_pair(in[out[v]], out[v]));
            in[out[v]]--;
            st.insert(make_pair(in[out[v]], out[v]));
            out[v] = u;
            ans++;
        }
        st.erase(make_pair(in[v], v));
        changed[u] = changed[v] = true;
    }
    cout << ans + count(changed.begin(), changed.end(), false);
}

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