oj.uz

Submission #1057816

# Submission time Handle Problem Language Result Execution time Memory
1057816 2024-08-14T06:25:10 Z Ignut Beech Tree (IOI23_beechtree) C++17
9 / 100
 2000 ms 48216 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);
    for (int i = 1; i < N; i ++) {
        tree[i].push_back(P[i]);
        tree[P[i]].push_back(i);
    }
    dfs(0);
    return res;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5724 KB Output is correct
2 Execution timed out 2093 ms 5724 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5720 KB Output is correct
2 Correct 1 ms 5724 KB Output is correct
3 Correct 1 ms 5724 KB Output is correct
4 Correct 1 ms 5724 KB Output is correct
5 Correct 1 ms 5724 KB Output is correct
6 Correct 1 ms 5748 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 5724 KB Output is correct
10 Correct 1 ms 5724 KB Output is correct
11 Correct 1 ms 5724 KB Output is correct
12 Correct 2 ms 5724 KB Output is correct
13 Correct 2 ms 6232 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 5724 KB Output is correct
18 Correct 1 ms 5976 KB Output is correct
19 Correct 1 ms 5720 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 Correct 1 ms 5724 KB Output is correct
26 Correct 1 ms 5752 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 5980 KB Output is correct
30 Correct 2 ms 5724 KB Output is correct
31 Correct 2 ms 5724 KB Output is correct
32 Correct 1 ms 5720 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 5720 KB Output is correct
2 Correct 1 ms 5724 KB Output is correct
3 Correct 1 ms 5724 KB Output is correct
4 Correct 1 ms 5724 KB Output is correct
5 Correct 1 ms 5724 KB Output is correct
6 Correct 1 ms 5748 KB Output is correct
7 Execution timed out 2062 ms 48216 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2043 ms 5724 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5720 KB Output is correct
2 Correct 1 ms 5724 KB Output is correct
3 Correct 1 ms 5724 KB Output is correct
4 Correct 1 ms 5724 KB Output is correct
5 Execution timed out 2062 ms 48216 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5724 KB Output is correct
2 Execution timed out 2093 ms 5724 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5720 KB Output is correct
2 Correct 1 ms 5724 KB Output is correct
3 Correct 1 ms 5724 KB Output is correct
4 Correct 1 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 5724 KB Output is correct
8 Correct 2 ms 5724 KB Output is correct
9 Correct 2 ms 6232 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 5724 KB Output is correct
14 Correct 1 ms 5976 KB Output is correct
15 Correct 1 ms 5720 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 5724 KB Output is correct
22 Correct 1 ms 5752 KB Output is correct
23 Correct 1 ms 5724 KB Output is correct
24 Correct 1 ms 5724 KB Output is correct
25 Correct 45 ms 5980 KB Output is correct
26 Execution timed out 2011 ms 5976 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #7
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5724 KB Output is correct
2 Execution timed out 2093 ms 5724 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5720 KB Output is correct
2 Correct 1 ms 5724 KB Output is correct
3 Correct 1 ms 5724 KB Output is correct
4 Correct 1 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 5724 KB Output is correct
8 Correct 2 ms 5724 KB Output is correct
9 Correct 2 ms 6232 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 5724 KB Output is correct
14 Correct 1 ms 5976 KB Output is correct
15 Correct 1 ms 5720 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 5724 KB Output is correct
22 Correct 1 ms 5752 KB Output is correct
23 Correct 1 ms 5724 KB Output is correct
24 Correct 1 ms 5724 KB Output is correct
25 Correct 45 ms 5980 KB Output is correct
26 Execution timed out 2011 ms 5976 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #9
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5724 KB Output is correct
2 Execution timed out 2093 ms 5724 KB Time limit exceeded
3 Halted 0 ms 0 KB -