oj.uz

Submission #1058055

# Submission time Handle Problem Language Result Execution time Memory
1058055 2024-08-14T08:09:10 Z Ignut Beech Tree (IOI23_beechtree) C++17
9 / 100
 34 ms 11860 KB 
/* Ignut
started: 14.08.2024
now: 14.08.2024
████████████████████████████████████████████████████████████████████
████████████████████████████████    ████████████████████████████████
██████████████████████████████        ██████████████████████████████
██████      ██████████████████        ██████████████████      ██████
██████          ██████████████        ██████████████          ██████
██████      ██    ████████████        ████████████    ██      ██████
██████      ████    ██████████        ██████████    ████      ██████
██████      ████      ██████████    ██████████      ████      ██████
██████      ████      ██████████    ██████████    ██████      ██████
██████      ██████    ██████████    ██████████    ██████      ██████
██████      ██████    ████████        ████████    ██████      ██████
██████      ██████      ██████        ██████      ██████      ██████
██████      ████        ████            ████        ████      ██████
██████            ██████████    ████    ██████████            ██████
██████      ██      ██████    ████████    ██████      ██      ██████
██████      ██████            ████████            ██████      ██████
██████                    ██            ██                    ██████
██████████████████████      ████    ████      ██████████████████████
████████████████████████      ██    ██      ████████████████████████
██████████████████████████                ██████████████████████████
██████████████████████████████        ██████████████████████████████
████████████████████████████████████████████████████████████████████
*/
 
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;

const int MAXN = 2e5 + 123;
int n;

vector<int> tree[MAXN];
vector<int> p;
vector<int> c;

vector<int> res;

int cnt[MAXN] = {};

bool Check(vector<int> &lst, int root) {
    // if (root == 4) {
    //     cout << root << " :\n";
    // }
    sort(lst.begin(), lst.end());
    do {
        bool ok = true;
        for (int v : lst) {
            int par = cnt[c[v]];
            int vert = (par == 0 ? root : lst[par - 1]);
            // if (root == 4) {
            //     cout << v << " -> " << par << ", ";
            // }
            if (p[v] != vert) {
                ok = false; break;
            }
            cnt[c[v]] ++;
        }
        // if (root == 4) {
        //     cout << '\n';
        // }
        for (int v : lst) cnt[c[v]] = 0;
        if (ok) return true;
    } while (next_permutation(lst.begin(), lst.end()));
    return false;
}

vector<int> dfs(int v) {
    vector<int> lst = {};
    for (int to : tree[v])
        if (to != p[v])
            for (int u : dfs(to))
                lst.push_back(u);
    res[v] |= Check(lst, v);
    lst.push_back(v);
    return lst;
}

vector<int> beechtree(int N, int M, vector<int> P, vector<int> C) {
    n = N; p = P; c = C;
    res.assign(N, 0);
    if (N <= 8) {
        // cout << "brute\n";
        for (int i = 1; i < N; i ++) {
            tree[i].push_back(P[i]);
            tree[P[i]].push_back(i);
        }
        dfs(0);
        return res;
    }
    int cnt = 0;
    for (int i = 1; i < N; i ++) cnt += (P[i] != 0);
    if (cnt <= 1) res[0] = 1;
    for (int i = 1; i < N; i ++) res[i] = 1;
    return res;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5720 KB Output is correct
2 Incorrect 1 ms 5724 KB 2nd lines differ - on the 4th token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5724 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 1 ms 5724 KB Output is correct
4 Correct 2 ms 5724 KB Output is correct
5 Correct 1 ms 5724 KB Output is correct
6 Correct 1 ms 5724 KB Output is correct
7 Correct 1 ms 5548 KB Output is correct
8 Correct 1 ms 5724 KB Output is correct
9 Correct 1 ms 5720 KB Output is correct
10 Correct 1 ms 5724 KB Output is correct
11 Correct 1 ms 5724 KB Output is correct
12 Correct 1 ms 5724 KB Output is correct
13 Correct 1 ms 5552 KB Output is correct
14 Correct 1 ms 5724 KB Output is correct
15 Correct 1 ms 5976 KB Output is correct
16 Correct 1 ms 5724 KB Output is correct
17 Correct 1 ms 5724 KB Output is correct
18 Correct 1 ms 5724 KB Output is correct
19 Correct 1 ms 5724 KB Output is correct
20 Correct 1 ms 5724 KB Output is correct
21 Correct 1 ms 5508 KB Output is correct
22 Correct 2 ms 5724 KB Output is correct
23 Correct 1 ms 5724 KB Output is correct
24 Correct 1 ms 5724 KB Output is correct
25 Correct 1 ms 5724 KB Output is correct
26 Correct 1 ms 5724 KB Output is correct
27 Correct 1 ms 5724 KB Output is correct
28 Correct 1 ms 5724 KB Output is correct
29 Correct 1 ms 5724 KB Output is correct
30 Correct 1 ms 5724 KB Output is correct
31 Correct 1 ms 5724 KB Output is correct
32 Correct 1 ms 5724 KB Output is correct
33 Correct 1 ms 5724 KB Output is correct
34 Correct 1 ms 5724 KB Output is correct

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5724 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 1 ms 5724 KB Output is correct
4 Correct 2 ms 5724 KB Output is correct
5 Correct 1 ms 5724 KB Output is correct
6 Correct 1 ms 5724 KB Output is correct
7 Incorrect 34 ms 11860 KB 2nd lines differ - on the 2nd token, expected: '0', found: '1'
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5724 KB Output is correct
2 Incorrect 1 ms 5724 KB 2nd lines differ - on the 4th token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5724 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 1 ms 5548 KB Output is correct
4 Correct 1 ms 5724 KB Output is correct
5 Incorrect 34 ms 11860 KB 2nd lines differ - on the 2nd token, expected: '0', found: '1'
6 Halted 0 ms 0 KB -

Subtask #5
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5720 KB Output is correct
2 Incorrect 1 ms 5724 KB 2nd lines differ - on the 4th token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5724 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 1 ms 5548 KB Output is correct
4 Correct 1 ms 5724 KB Output is correct
5 Correct 1 ms 5720 KB Output is correct
6 Correct 1 ms 5724 KB Output is correct
7 Correct 1 ms 5724 KB Output is correct
8 Correct 1 ms 5724 KB Output is correct
9 Correct 1 ms 5552 KB Output is correct
10 Correct 1 ms 5724 KB Output is correct
11 Correct 1 ms 5976 KB Output is correct
12 Correct 1 ms 5724 KB Output is correct
13 Correct 1 ms 5724 KB Output is correct
14 Correct 1 ms 5724 KB Output is correct
15 Correct 1 ms 5724 KB Output is correct
16 Correct 1 ms 5724 KB Output is correct
17 Correct 1 ms 5508 KB Output is correct
18 Correct 2 ms 5724 KB Output is correct
19 Correct 1 ms 5724 KB Output is correct
20 Correct 1 ms 5724 KB Output is correct
21 Correct 1 ms 5724 KB Output is correct
22 Correct 1 ms 5724 KB Output is correct
23 Correct 1 ms 5724 KB Output is correct
24 Correct 1 ms 5724 KB Output is correct
25 Incorrect 2 ms 5976 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
26 Halted 0 ms 0 KB -

Subtask #7
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5720 KB Output is correct
2 Incorrect 1 ms 5724 KB 2nd lines differ - on the 4th token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -

Subtask #8
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5724 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 1 ms 5548 KB Output is correct
4 Correct 1 ms 5724 KB Output is correct
5 Correct 1 ms 5720 KB Output is correct
6 Correct 1 ms 5724 KB Output is correct
7 Correct 1 ms 5724 KB Output is correct
8 Correct 1 ms 5724 KB Output is correct
9 Correct 1 ms 5552 KB Output is correct
10 Correct 1 ms 5724 KB Output is correct
11 Correct 1 ms 5976 KB Output is correct
12 Correct 1 ms 5724 KB Output is correct
13 Correct 1 ms 5724 KB Output is correct
14 Correct 1 ms 5724 KB Output is correct
15 Correct 1 ms 5724 KB Output is correct
16 Correct 1 ms 5724 KB Output is correct
17 Correct 1 ms 5508 KB Output is correct
18 Correct 2 ms 5724 KB Output is correct
19 Correct 1 ms 5724 KB Output is correct
20 Correct 1 ms 5724 KB Output is correct
21 Correct 1 ms 5724 KB Output is correct
22 Correct 1 ms 5724 KB Output is correct
23 Correct 1 ms 5724 KB Output is correct
24 Correct 1 ms 5724 KB Output is correct
25 Incorrect 2 ms 5976 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
26 Halted 0 ms 0 KB -

Subtask #9
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5720 KB Output is correct
2 Incorrect 1 ms 5724 KB 2nd lines differ - on the 4th token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -