oj.uz

Submission #841447

# Submission time Handle Problem Language Result Execution time Memory
841447 2023-09-01T15:40:26 Z model_code Beech Tree (IOI23_beechtree) C++17
17 / 100
 2000 ms 313000 KB 
// failed/subtask-mediumN-1-wa2.cpp

#include "beechtree.h"

#include <set>
#include <algorithm>

using namespace std;
using pii = pair<int, int>;

int n, m;
vector<int> par, sz;
vector<set<int>> ch_colors;
vector<vector<int>> ch, ord;
vector<int> t;

bool is_subset(int x, int y)
{
    if (ch_colors[x].size() > ch_colors[y].size() || (sz[x] == sz[y] && ch_colors[x].size() != ch_colors[y].size()))
        return false;
    for (int c : ch_colors[x])
    {
        if (!ch_colors[y].count(c))
            return false;
    }
    return true;
}

void dfs(int u)
{
    for (int v : ch[u])
    {
        dfs(v);
        if (t[v] == 0)
        {
            t[u] = 0;
        }
    }
    if (t[u] == 0)
        return;
    ord[u] = {u};
    for (int v : ch[u])
        ord[u].insert(ord[u].end(), ord[v].begin(), ord[v].end());
    sort(ord[u].begin(), ord[u].end(), [&](int x, int y)
         {
        if (sz[x] != sz[y])
            return sz[x] < sz[y];
        return x > y; });
    int k = ord[u].size();
    for (int i = 0; i + 1 < k; ++i)
    {
        int x = ord[u][i], y = ord[u][i + 1];
        if (!is_subset(x, y))
        {
            t[u] = 0;
            return;
        }
    }
}

std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C)
{
    n = N, m = M, par = P;
    ord.assign(N, {});
    ch.assign(N, {});
    ch_colors.assign(N, {});
    t.assign(N, 1);
    for (int v = 1; v < N; ++v)
    {
        int u = P[v];
        if (ch_colors[u].count(C[v]))
        {
            t[u] = 0;
        }
        ch[u].push_back(v);
        ch_colors[u].insert(C[v]);
    }
    for (int v = 1; v < N; ++v)
    {
        if (ch_colors[v].size() > ch_colors[P[v]].size())
            t[P[v]] = 0;
    }
    sz.assign(N, 1);
    for (int v = N - 1; v > 0; --v)
    {
        sz[P[v]] += sz[v];
    }
    dfs(0);

    return t;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 216 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 0 ms 212 KB Output is correct

Subtask #1
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 216 KB Output is correct
3 Correct 0 ms 216 KB Output is correct
4 Correct 0 ms 220 KB Output is correct
5 Correct 0 ms 216 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 216 KB Output is correct
8 Correct 0 ms 216 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Incorrect 0 ms 212 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
19 Halted 0 ms 0 KB -

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 216 KB Output is correct
3 Correct 0 ms 216 KB Output is correct
4 Correct 0 ms 220 KB Output is correct
5 Correct 0 ms 216 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 91 ms 71600 KB Output is correct
8 Correct 90 ms 71596 KB Output is correct
9 Correct 1 ms 416 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 288 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 42 ms 8780 KB Output is correct
14 Correct 34 ms 4940 KB Output is correct
15 Correct 1 ms 980 KB Output is correct
16 Correct 1 ms 964 KB Output is correct
17 Execution timed out 2187 ms 313000 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1392 KB Output is correct
2 Correct 0 ms 224 KB Output is correct
3 Correct 1 ms 228 KB Output is correct
4 Correct 1 ms 228 KB Output is correct
5 Correct 0 ms 228 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 0 ms 228 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 2 ms 568 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 65 ms 24188 KB Output is correct
16 Correct 70 ms 22708 KB Output is correct
17 Correct 52 ms 22384 KB Output is correct
18 Correct 66 ms 23744 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 216 KB Output is correct
3 Correct 0 ms 216 KB Output is correct
4 Correct 0 ms 216 KB Output is correct
5 Correct 91 ms 71600 KB Output is correct
6 Correct 90 ms 71596 KB Output is correct
7 Correct 0 ms 228 KB Output is correct
8 Correct 1 ms 228 KB Output is correct
9 Correct 2 ms 736 KB Output is correct
10 Correct 2 ms 608 KB Output is correct
11 Correct 103 ms 46736 KB Output is correct
12 Correct 118 ms 41932 KB Output is correct

Subtask #5
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 216 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 216 KB Output is correct
6 Correct 0 ms 216 KB Output is correct
7 Correct 0 ms 220 KB Output is correct
8 Correct 0 ms 216 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 216 KB Output is correct
11 Correct 0 ms 216 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Incorrect 0 ms 212 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
22 Halted 0 ms 0 KB -

Subtask #6
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 216 KB Output is correct
3 Correct 0 ms 216 KB Output is correct
4 Correct 0 ms 216 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Incorrect 0 ms 212 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
15 Halted 0 ms 0 KB -

Subtask #7
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 216 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 216 KB Output is correct
6 Correct 0 ms 216 KB Output is correct
7 Correct 0 ms 220 KB Output is correct
8 Correct 0 ms 216 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 216 KB Output is correct
11 Correct 0 ms 216 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Incorrect 0 ms 212 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
22 Halted 0 ms 0 KB -

Subtask #8
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 216 KB Output is correct
3 Correct 0 ms 216 KB Output is correct
4 Correct 0 ms 216 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Incorrect 0 ms 212 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
15 Halted 0 ms 0 KB -

Subtask #9
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 216 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 216 KB Output is correct
6 Correct 0 ms 216 KB Output is correct
7 Correct 0 ms 220 KB Output is correct
8 Correct 0 ms 216 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 216 KB Output is correct
11 Correct 0 ms 216 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Incorrect 0 ms 212 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
22 Halted 0 ms 0 KB -