제출 #841421

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
841421		model_code	참나무 (IOI23_beechtree)	C++17	9 / 100	67 ms	23868 KiB

beechtree

// correct/subtask-shallow.cpp

#include "beechtree.h"

#include <set>
#include <algorithm>

using namespace std;

vector<int> beechtree(int N, int /*M*/, vector<int> P, vector<int> C)
{
    vector<set<int>> ch_colors(N);
    vector<int> t(N, true);
    for (int v = 1; v < N; ++v)
    {
        int u = P[v], c = C[v];
        if (ch_colors[u].count(c))
        {
            t[u] = false;
            if (u > 0)
                t[0] = false;
        }
        else
            ch_colors[u].insert(c);
    }

    vector<int> ord(N);
    for (int i = 0; i < N; ++i)
        ord[i] = i;
    sort(ord.begin(), ord.end(), [&](int u, int v)
         {
        if (ch_colors[u].size() != ch_colors[v].size())
            return ch_colors[u].size() < ch_colors[v].size();
        return u > v; });
    if (ord[N - 1] != 0)
        t[0] = false;
    for (int i = 0; i + 1 < N; ++i)
    {
        int u = ord[i], v = ord[i + 1];
        for (int c : ch_colors[u])
        {
            if (!ch_colors[v].count(c))
                t[0] = false;
        }
    }

    return t;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 9
• Subtask 2: 0 / 5
• Subtask 3: 9 / 9
• Subtask 4: 0 / 8
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 12
• Subtask 8: 0 / 17
• Subtask 9: 0 / 12