Submission #651080

#	Time	Username	Problem	Language	Result	Execution time	Memory
651080		dooompy	Love Polygon (BOI18_polygon)	C++17	100 / 100	515 ms	23256 KiB

polygon

#include <bits/stdc++.h>

using namespace std;

map<string, int> conv;
int id = 1;

struct node {
    int edge;
    set<int> redge; // loved by
};

node nodes[100005];
bool matched[100005];
bool seen[100005];

int ans = 0;
int ct = 0;

void dfs(int i) {
    if (seen[i]) return;

    seen[i] = true;
    ct++;
    dfs(nodes[i].edge);
}

int main() {
    int n; cin >> n;

    if (n % 2 == 1) {
        cout << "-1"; return 0;
    }

    for (int i = 0; i < n; i++) {
        string a, b; cin >> a >> b;

        // a loves b

        if (conv.find(a) == conv.end()) conv[a] = id++;
        if (conv.find(b) == conv.end()) conv[b] = id++;

        nodes[conv[a]].edge = conv[b];
        nodes[conv[b]].redge.insert(conv[a]);

        if (conv[a] != conv[b] && nodes[conv[b]].edge == conv[a]) {
            matched[conv[a]] = matched[conv[b]] = true;
        }
    }

    queue<int> leafs;

    for (int i = 1; i <= n; i++) {
        if (nodes[i].redge.size() == 0) leafs.push(i);
    }

    set<int> loners;

    while (!leafs.empty()) {
        auto top = leafs.front(); leafs.pop();

        if (matched[nodes[top].edge]) {
            // sad

            loners.insert(top);
        } else {
            // match them

            int to = nodes[top].edge;
            int removenode = nodes[to].edge;

            nodes[removenode].redge.erase(to);
            if (nodes[removenode].redge.size() == 0) {
                leafs.push(removenode);
            }

            ans++;

            matched[to] = matched[top] = true;
        }
    }

    vector<int> cycle;


    for (int i = 1; i <= n; i++) {
        if (matched[i]) seen[i] = true;
    }

    for (int i = 1; i <= n; i++) {
        if (seen[i] || loners.find(i) != loners.end()) continue;

        ct = 0;
        dfs(i);
        cycle.push_back(ct);
    }

    int lonersz = loners.size();
    for (auto cur : cycle) {
        if (cur == 1) lonersz++;
        else if (cur == 2) continue;
        else {
            ans += (cur / 2);
            if (cur % 2 == 1) lonersz++;
        }
    }

    ans += (lonersz);

    cout << ans;
}

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