Submission #4639983

---

Source Code Expand

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

const int N = 1e5 + 100;

int n, fa[N], fb[N], is_odd[2][N];

struct Edge {
    int e, *h, *nx, *to, V, E;
    Edge(int V, int E):V(V), E(E) {
        e = 0;
        h = new int [V];
        nx = new int [E];
        to = new int [E];
        memset(h, -1, 4 * V);
    }
    ~Edge() {
        delete h;
        delete nx;
        delete to;
    }
    void clear() {
        e = 0;
        memset(h, -1, 4 * V);
    }
    void add(int u, int v) {
        to[e] = v, nx[e] = h[u], h[u] = e++;
        to[e] = u, nx[e] = h[v], h[v] = e++;
    }
} *tr, *bi;

int dfs(int u, int f) {
    vector<int> odd_son;
    for (int i = tr->h[u]; i != -1; i = tr->nx[i]) {
        int v = tr->to[i];
        if (v != f) {
            v = dfs(v, u);
            if (v != 0)
                odd_son.push_back(v);
            else cassert(false);
        }
    }
    if (!is_odd[0][u])
        odd_son.push_back(u);
    for (int i = 0; i < (int)odd_son.size() - 1; i += 2) {
        bi->add(odd_son[i], odd_son[i + 1]);
    }
    return odd_son.size() % 2 == 0 ? 0 : odd_son.back();
}

bool vis[N], col[N];

void coloring(int u, int c) {
    vis[u] = true;
    col[u] = c;
    for (int i = bi->h[u]; i != -1; i = bi->nx[i]) {
        int v = bi->to[i];
        if (!vis[v])
            coloring(v, c ^ 1);
    }
}

int main() {
#ifdef lol
    freopen("f.in", "r", stdin);
    freopen("f.out", "w", stdout);
#endif

    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &fa[i]);
        if (fa[i] != -1) {
            is_odd[0][fa[i]] ^= 1;
        }
    }
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &fb[i]);
        if (fb[i] != -1)
            is_odd[1][fb[i]] ^= 1;
    }
    for (int i = 1; i <= n; ++i) {
        if (is_odd[0][i] ^ is_odd[1][i]) {
            puts("IMPOSSIBLE");
            return 0;
        }
    }
    tr = new Edge(n + 1, (n + 1) * 2);
    bi = new Edge(n + 10, (n + 10) * 4);
    int rt;
    for (int i = 1; i <= n; ++i) {
        if (fa[i] == -1) {
            rt = i;
            continue;
        }
        tr->add(i, fa[i]);
    }
    dfs(rt, -1);
    tr->clear();
    for (int i = 1; i <= n; ++i) {
        if (fb[i] == -1) {
            rt = i;
            continue;
        }
        tr->add(i, fb[i]);
    }
    dfs(rt, -1);
    for (int i = 1; i <= n; ++i)
        if (!vis[i]) {
            coloring(i, 1);
        }
    puts("POSSIBLE");
    for (int i = 1; i <= n; ++i) {
        if (is_odd[0][i]) {
            printf("%d ", 0);
        } else {
            printf("%d ", col[i] ? 1 : -1);
        }
    }
    puts("");

    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int dfs(int, int)’:
./Main.cpp:40:31: error: ‘cassert’ was not declared in this scope
             else cassert(false);
                               ^
./Main.cpp: In function ‘int main()’:
./Main.cpp:69:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
./Main.cpp:71:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &fa[i]);
                            ^
./Main.cpp:77:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &fb[i]);
                            ^