oj.uz

Submission #1038892

# Submission time Handle Problem Language Result Execution time Memory
1038892 2024-07-30T08:42:11 Z fv3 Beech Tree (IOI23_beechtree) C++17
9 / 100
 55 ms 17604 KB 
#include <bits/stdc++.h>
#include "beechtree.h"

using namespace std;

vector<int> beechtree(int N, int M, vector<int> P, vector<int> C)
{
    vector<int> b(N);
    vector<vector<int>> adj(N);

    for (int i = 1; i < N; i++)
    {
        adj[P[i]].push_back(i);
    }

    map<int, int> colourCnt;
    for (auto node : adj[0])
    {
        b[node] = 1;
        set<int> childColours;
        for (auto e : adj[node])
        {
            if (childColours.count(C[e])) 
                b[node] = 0;
            childColours.insert(C[e]);
            colourCnt[C[e]]++;
            b[e] = 1;
        }
    }

    b[0] = 1;
    set<int> childColours;
    map<int, int> ncnt;
    for (auto node : adj[0])
    {
        if (!b[node] || childColours.count(C[node]))
        {
            b[0] = 0;
            break;
        } 
        childColours.insert(C[node]);
        ncnt[C[node]]++;
    }

    vector<int> cnts;
    for (auto n : colourCnt)
    {
        if (childColours.count(n.first) == 0)
        {
            b[0] = 0;
            break;
        }
        cnts.push_back(n.second);
    }

    vector<pair<int, int>> pi;
    for (auto node : adj[0])
    {
        pi.push_back({adj[node].size(), node});
    }

    sort(pi.begin(), pi.end());
    reverse(pi.begin(), pi.end());

    int d = 1;
    for (auto subtree : pi)
    {
        for (auto node : adj[subtree.second])
        {
            if (ncnt[C[node]]++ != d)
            {
                b[0] = 0;
                return b;
            }
        }

        d++;
    }

    return b;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Incorrect 1 ms 348 KB 2nd lines differ - on the 4th 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 0 ms 348 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Incorrect 1 ms 348 KB 2nd lines differ - on the 4th 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 0 ms 432 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 51 ms 6412 KB Output is correct
16 Correct 49 ms 6220 KB Output is correct
17 Correct 38 ms 6320 KB Output is correct
18 Correct 40 ms 6472 KB Output is correct

Subtask #4
0.0 / 8.0

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