lessons/参考实现/01-欧拉路径/AtCoder-agc018_f.cpp

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int to;
    int id;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> parent_a(n), parent_b(n);
    for (int &x : parent_a) {
        cin >> x;
        if (x != -1) --x;
    }
    for (int &x : parent_b) {
        cin >> x;
        if (x != -1) --x;
    }

    vector<int> children_a(n), children_b(n);
    int root_a = -1, root_b = -1;
    for (int v = 0; v < n; ++v) {
        if (parent_a[v] == -1) root_a = v;
        else ++children_a[parent_a[v]];
        if (parent_b[v] == -1) root_b = v;
        else ++children_b[parent_b[v]];
    }
    for (int v = 0; v < n; ++v) {
        if ((children_a[v] & 1) != (children_b[v] & 1)) {
            cout << "IMPOSSIBLE\n";
            return 0;
        }
    }

    const int extra = 2 * n;
    vector<vector<Edge>> graph(2 * n + 1);
    vector<pair<int, int>> endpoints;
    vector<int> cross_vertex;
    auto add_edge = [&](int u, int v, int owner) {
        int id = static_cast<int>(endpoints.size());
        endpoints.push_back({u, v});
        cross_vertex.push_back(owner);
        graph[u].push_back({v, id});
        graph[v].push_back({u, id});
    };

    for (int v = 0; v < n; ++v) {
        if (parent_a[v] != -1) add_edge(v, parent_a[v], -1);
        if (parent_b[v] != -1) add_edge(n + v, n + parent_b[v], -1);
    }
    add_edge(root_a, extra, -1);
    add_edge(n + root_b, extra, -1);
    for (int v = 0; v < n; ++v) {
        if ((children_a[v] & 1) == 0) add_edge(v, n + v, v);
    }

    vector<int> answer(n, 0), cursor(graph.size(), 0), stack = {extra};
    vector<char> used(endpoints.size(), false);
    while (!stack.empty()) {
        int v = stack.back();
        while (cursor[v] < static_cast<int>(graph[v].size()) &&
               used[graph[v][cursor[v]].id]) {
            ++cursor[v];
        }
        if (cursor[v] == static_cast<int>(graph[v].size())) {
            stack.pop_back();
            continue;
        }
        Edge e = graph[v][cursor[v]++];
        if (used[e.id]) continue;
        used[e.id] = true;
        int owner = cross_vertex[e.id];
        if (owner != -1) answer[owner] = (v == owner ? 1 : -1);
        stack.push_back(e.to);
    }

    cout << "POSSIBLE\n";
    for (int i = 0; i < n; ++i) {
        if (i) cout << ' ';
        cout << answer[i];
    }
    cout << '\n';
    return 0;
}