Submission #1449376

---

Source Code Expand

#include <bits/stdc++.h>

#define mp make_pair
#define pb push_back


typedef long long ll;
typedef long long llong;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;

template <typename T> void dprint(T begin, T end) {
    for (auto i = begin; i != end; i++) {
        cerr << (*i) << " ";
    }
    cerr << "\n";
}
const int MAXN = 120000;

vector<int> ea[MAXN];
vector<int> eb[MAXN];
vector<int> eds[MAXN];
int cl[MAXN];
int was[MAXN];

void add_edge(int a, int b) {
    eds[a].push_back(b);
    eds[b].push_back(a);
}

int dfs1(int v) {
    for (int i = 0; i + 1 < ea[v].size(); i += 2)
        add_edge(dfs1(ea[v][i]), dfs1(ea[v][i + 1]));
    if (ea[v].size() % 2 == 0)
        return v;
    else
        return dfs1(ea[v].back());
}

int dfs2(int v) {
    for (int i = 0; i + 1 < eb[v].size(); i += 2)
        add_edge(dfs2(eb[v][i]), dfs2(eb[v][i + 1]));
    if (eb[v].size() % 2 == 0)
        return v;
    else
        return dfs2(eb[v].back());
}

void dfs3(int v, int c) {
    was[v] = 1;
    cl[v] = c;
    for (int u: eds[v]) {
        if (was[u])
            continue;
        dfs3(u, c ^ 1);
    }
}

int n;

int main() {
    scanf("%d", &n);
    int ra = -1, rb = -1;
    for (int i = 0; i < n; ++i) {
        int p;
        scanf("%d", &p);
        --p;
        if (p == -2)
            ra = i;
        else
            ea[p].push_back(i);
    }
    for (int i = 0; i < n; ++i) {
        int p;
        scanf("%d", &p);
        --p;
        if (p == -2)
            rb = i;
        else
            eb[p].push_back(i);
    }
    for (int i = 0; i < n; ++i) {
        if (ea[i].size() % 2 != eb[i].size() % 2) {
            cout << "IMPOSSIBLE\n";
            return 0;
        }
    }
    dfs1(ra);
    dfs2(rb);
    printf("POSSIBLE\n");
    for (int i = 0; i < n; ++i) {
        if (!was[i]) {
            dfs3(i, 0);
        }
    }
    for (int i = 0; i < n; ++i) {
        if (ea[i].size() % 2 == 1) {
            printf("0 ");
        }
        else {
            if (cl[i] == 0)
                printf("-1 ");
            else
                printf("1 ");
        }
    }
    printf("\n");
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:64:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
./Main.cpp:68:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &p);
                        ^
./Main.cpp:77:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &p);
                        ^

Judge Result