3915 2023. 03. 05 13:02:18 zsombor Különböző katicák cpp17 Accepted 100/100 87ms 36760 KiB 
#include <iostream>
#include <vector>
using namespace std;

int n;
bool lehet = true;
vector <vector <int>> g(1e5 + 1);
vector <int> f(1e5 + 1, 0);
vector <int> p(1e5 + 1, -1);
vector <int> mn(1e5 + 1, -1e9);
vector <int> mx(1e5 + 1, 1e9);
vector <int> par(1e5 + 1, -1);

void dfs1(int x) {
    if (p[x] > -1) {
        mn[x] = mx[x] = p[x];
        par[x] = p[x] % 2;
    }
    for (int i : g[x]) {
        dfs1(i);
        mn[x] = max(mn[x], mn[i] - 1);
        mx[x] = min(mx[x], mx[i] + 1);
        if (par[x] == -1 && par[i] > -1) par[x] = 1 - par[i];
        if (par[x] > -1 && par[i] > -1 && par[x] == par[i]) lehet = false;
    }
    if (mn[x] > mx[x]) lehet = false;
}

void dfs2(int x) {
    if (p[x] == -1) p[x] = (p[f[x]] + 1 <= mx[x] ? p[f[x]] + 1 : p[f[x]] - 1);
    for (int i : g[x]) dfs2(i);
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> f[i];
        g[f[i]].push_back(i);
    }
    for (int i = 1; i <= n; i++) cin >> p[i];
    dfs1(1);
    if (!lehet) { cout << "NEM"; return 0; }
    p[1] = (par[1] == -1 ? 0 : mn[1]);
    dfs2(1);
    cout << "IGEN\n";
    for (int i = 1; i <= n; i++) cout << p[i] << " ";
}
Subtask Sum Test Verdict Time Memory
subtask1 0/0
1 Accepted 7ms 10180 KiB
2 Accepted 6ms 10452 KiB
3 Accepted 71ms 14428 KiB
subtask2 10/10
4 Accepted 64ms 14160 KiB
5 Accepted 68ms 14848 KiB
6 Accepted 75ms 15408 KiB
7 Accepted 81ms 15748 KiB
subtask3 15/15
8 Accepted 71ms 35800 KiB
9 Accepted 68ms 35632 KiB
10 Accepted 87ms 36760 KiB
11 Accepted 82ms 36076 KiB
12 Accepted 82ms 35296 KiB
13 Accepted 83ms 36244 KiB
14 Accepted 78ms 34840 KiB
subtask4 35/35
15 Accepted 7ms 12488 KiB
16 Accepted 6ms 12616 KiB
17 Accepted 6ms 12700 KiB
18 Accepted 6ms 12836 KiB
19 Accepted 6ms 12780 KiB
20 Accepted 6ms 12780 KiB
21 Accepted 6ms 12912 KiB
22 Accepted 6ms 12900 KiB
subtask5 40/40
23 Accepted 74ms 16548 KiB
24 Accepted 65ms 16680 KiB
25 Accepted 67ms 16680 KiB
26 Accepted 75ms 16552 KiB
27 Accepted 75ms 16548 KiB
28 Accepted 82ms 16680 KiB
29 Accepted 82ms 16700 KiB
30 Accepted 79ms 16836 KiB
31 Accepted 76ms 16816 KiB
32 Accepted 81ms 16924 KiB
33 Accepted 86ms 16924 KiB