제출 #912604

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
912604		Ludissey	참나무 (IOI23_beechtree)	C++17	0 / 100	1 ms	348 KiB

beechtree

#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;
int N,M;
vector<vector<int>> child;
vector<int> C;
vector<int> P;
vector<int> outp;


std::vector<int> beechtree(int n, int m, std::vector<int> p, std::vector<int> c)
{
    N=n; M=m;
    C.assign(c.begin(), c.end());
    P.assign(p.begin(), p.end());
    child.resize(n);
    outp.resize(n,0);
    P[0]=0;
    vector<int> depth(N,0);
    vector<bool> triple(N);
    for (int i = 1; i < N; i++) child[P[i]].push_back(i);
    for (int i = 1; i < N; i++) if(P[P[i]]!=0) triple[P[P[i]]]=true;

    for (int i = 0; i < n; i++)
    {
        if(child[i].size()>2||triple[i]) continue;
        else if(child[i].size()==0) outp[i]=1;
        else if(child[i].size()==2) {
            unordered_set<int> childColor;
            for (auto u : child[i]) childColor.insert(c[u]);
            unordered_set<int> child1Color;
            unordered_set<int> child2Color;
            if(triple[i]||childColor.size()!=2||(child[child[i][0]].size()+child[child[i][1]].size())>2) continue;
            for (auto u : child[child[i][0]])
            {
                child1Color.insert(c[u]);
                childColor.insert(c[u]);
            }
            if(child1Color.size()!=child[child[i][0]].size()) continue;
            for (auto u : child[child[i][1]])
            {
                child1Color.insert(c[u]);
                child2Color.insert(c[u]);
                childColor.insert(c[u]);
            }
            if(child2Color.size()!=child[child[i][1]].size()) continue;
            if(child1Color.size()!=child[child[i][0]].size()+child[child[i][1]].size()) continue;
            if(childColor.size()!=2) continue;
            outp[i]=1;
        }else{
            if(triple[i]) continue;
            outp[i]=1;
            int u=i;
            int l=c[u];
            while(child[u].size()>0){
                if(child[u].size()!=1||l!=c[u]) { outp[i]=0; break; }
                u=child[u][0];
                l=c[u];
            }
        }
    }
    return {outp};
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 9
• Subtask 2: 0 / 5
• Subtask 3: 0 / 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