oj.uz

Submission #841449

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

#include "beechtree.h"

#include <set>
#include <algorithm>

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

int n, m;
vector<int> par;
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())
        swap(x, y);
    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 (ch_colors[x].size() != ch_colors[y].size())
            return ch_colors[x].size() < ch_colors[y].size();
        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;
    }
    dfs(0);

    return t;
}

Subtask #0
0.0 / 0.0

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

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 212 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 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Incorrect 0 ms 212 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
10 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 212 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 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 103 ms 68280 KB Output is correct
8 Correct 103 ms 68368 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 43 ms 8688 KB Output is correct
14 Correct 23 ms 4940 KB Output is correct
15 Correct 1 ms 980 KB Output is correct
16 Correct 2 ms 920 KB Output is correct
17 Execution timed out 2053 ms 372596 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 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 0 ms 212 KB Output is correct
11 Correct 1 ms 468 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 66 ms 22692 KB Output is correct
16 Correct 75 ms 21276 KB Output is correct
17 Correct 50 ms 21076 KB Output is correct
18 Correct 71 ms 22308 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 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 103 ms 68280 KB Output is correct
6 Correct 103 ms 68368 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 113 ms 43408 KB Output is correct
12 Correct 124 ms 38768 KB Output is correct

Subtask #5
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 240 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
4 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 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 0 ms 212 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
6 Halted 0 ms 0 KB -

Subtask #7
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 240 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
4 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 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 0 ms 212 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
6 Halted 0 ms 0 KB -

Subtask #9
0.0 / 12.0

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