oj.uz

Submission #651067

# Submission time Handle Problem Language Result Execution time Memory
651067 2022-10-16T23:56:36 Z dooompy Love Polygon (BOI18_polygon) C++17
0 / 100
 390 ms 20648 KB 
#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 (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 (seen[i] || matched[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 (ans % 2 == 1) lonersz++;
        }
    }

    ans += (lonersz);

    cout << ans;


}

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5780 KB Output is correct
2 Correct 3 ms 5732 KB Output is correct
3 Incorrect 3 ms 5784 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 390 ms 20648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5780 KB Output is correct
2 Correct 3 ms 5732 KB Output is correct
3 Incorrect 3 ms 5784 KB Output isn't correct
4 Halted 0 ms 0 KB -