oj.uz

Submission #1038916

# Submission time Handle Problem Language Result Execution time Memory
1038916 2024-07-30T09:08:54 Z fv3 Beech Tree (IOI23_beechtree) C++17
9 / 100
 66 ms 47332 KB 
#include <bits/stdc++.h>
#include "beechtree.h"

using namespace std;
vector<int> b;
vector<int> leafDist;
vector<set<int>> vs;
vector<vector<int>> adj;

void DFS(int index, vector<int>&C)
{
    b[index] = 1;
    if (adj[index].size() == 0)
        return;

    for (auto node : adj[index])
    {
        DFS(node, C);
        leafDist[index] = max(leafDist[index], leafDist[node] + 1);
    }

    if (leafDist[index] == 1)
    {
        for (auto node : adj[index])
        {
            if (vs[index].count(C[node]))
                b[index] = 0;
            vs[index].insert(C[node]);
        }
    }
    else
        b[index] = 0;
}

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

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

    DFS(0, C);
    if (leafDist[0] <= 2)
    {
        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;

    }

    for (int i = 0; i < N; i++)
    {
        if (leafDist[i] != 2) continue;
        int index = -1;
        for (auto node : adj[i])
        {
            if (leafDist[node] == 1)
            {
                if (index != -1)
                {
                    index = -1;
                    break;
                }
                else
                {
                    index = node;
                }
            }
        }
        if (index == -1) continue;

        b[i] = 1;
        set<int> s;
        for (auto node : adj[index])
        {
            if (s.count(C[node]))
            {
                b[i] = 0;
                break;
            }
            s.insert(C[node]);
        }

        for (auto n : vs[index])
        {
            if (!s.count(n))
            {
                b[i] = 0;
                break;
            }
        }
    }

    return b;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
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 348 KB Output is correct
3 Incorrect 0 ms 348 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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 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 0 ms 348 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 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 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 0 ms 348 KB Output is correct
11 Correct 1 ms 440 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 52 ms 16976 KB Output is correct
16 Correct 48 ms 15992 KB Output is correct
17 Correct 41 ms 16212 KB Output is correct
18 Correct 51 ms 16692 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 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 66 ms 47332 KB 2nd lines differ - on the 199998th 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 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
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 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 0 ms 348 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 436 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Incorrect 0 ms 344 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 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
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 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 0 ms 348 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 436 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Incorrect 0 ms 344 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 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -