oj.uz

Submission #841414

# Submission time Handle Problem Language Result Execution time Memory
841414 2023-09-01T15:39:29 Z model_code Beech Tree (IOI23_beechtree) C++17
17 / 100
 114 ms 62616 KB 
// correct/subtask-colorTwice-2.cpp

#include "beechtree.h"

#include <set>
#include <algorithm>

using namespace std;

vector<int> t, dep;
vector<vector<int>> ch;
vector<set<int>> ch_colors;

void dfs(int u)
{
    for (int v : ch[u])
    {
        dfs(v);
        dep[u] = max(dep[u], dep[v] + 1);
        if (t[v] == 0)
            t[u] = 0;
    }
    if (dep[u] != 2)
    {
        if (dep[u] > 2)
            t[u] = 0;
        return;
    }
    vector<int> ord = ch[u];
    ord.push_back(u);
    sort(ord.begin(), ord.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; });
    if (ord.back() != u)
        t[u] = 0;
    for (int i = 0; i + 1 < (int)ord.size(); ++i)
    {
        int x = ord[i], y = ord[i + 1];
        for (int c : ch_colors[x])
        {
            if (!ch_colors[y].count(c))
                t[u] = 0;
        }
    }
}

vector<int> beechtree(int N, int /*M*/, vector<int> P, vector<int> C)
{
    t.assign(N, 1);
    ch.assign(N, {});
    ch_colors.resize(N);
    for (int v = 1; v < N; ++v)
    {
        int u = P[v], c = C[v];
        if (ch_colors[u].count(c))
            t[u] = false;
        ch[u].push_back(v);
        ch_colors[u].insert(c);
    }
    dep.assign(N, 0);
    dfs(0);

    return t;
}

Subtask #0
0.0 / 0.0

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

Subtask #2
0.0 / 5.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 212 KB Output is correct
5 Correct 1 ms 212 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 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 1 ms 468 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 464 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 51 ms 16908 KB Output is correct
16 Correct 53 ms 15676 KB Output is correct
17 Correct 48 ms 15900 KB Output is correct
18 Correct 62 ms 16148 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 107 ms 62616 KB Output is correct
6 Correct 98 ms 62520 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 2 ms 568 KB Output is correct
11 Correct 96 ms 34344 KB Output is correct
12 Correct 114 ms 30100 KB Output is correct

Subtask #5
0.0 / 14.0

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

Subtask #6
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 296 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 0 ms 212 KB Output is correct
9 Correct 1 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 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Incorrect 0 ms 212 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
17 Halted 0 ms 0 KB -

Subtask #7
0.0 / 12.0

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

Subtask #8
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 296 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 0 ms 212 KB Output is correct
9 Correct 1 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 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Incorrect 0 ms 212 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
17 Halted 0 ms 0 KB -

Subtask #9
0.0 / 12.0

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