제출 #1210718

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1210718		Nelt	참나무 (IOI23_beechtree)	C++20	0 / 100	3 ms	4936 KiB

beechtree

#include "beechtree.h"
#include <bits/stdc++.h>
#define endl "\n"
#define ll long long
using namespace std;
const ll N = 2e5 + 5;
vector<ll> g[N];
vector<int> ans;
ll c[N], p[N];
ll last[N], ptr[N], sub[N];
bool ok[N];
void dfs(ll v)
{
    sub[v] = 1;
    ok[v] = 1;
    for (ll to : g[v])
        dfs(to), sub[v] += sub[to], ok[v] &= ok[to];
    set<ll> s;
    for (ll to : g[v]) s.insert(c[to]);
    ok[v] &= s.size() == g[v].size();
}
vector<int> beechtree(int n, int m, vector<int> P, vector<int> C)
{
    for (ll i = 1; i <= n; i++)
        p[i] = P[i - 1] + 1, c[i] = C[i - 1];
    for (ll i = 2; i <= n; i++)
        g[p[i]].push_back(i);
    {
        vector<ll> b;
        for (ll i = 1; i <= n; i++)
            b.push_back(c[i]);
        sort(b.begin(), b.end());
        b.resize(unique(b.begin(), b.end()) - b.begin());
        for (ll i = 1; i <= n; i++)
            c[i] = lower_bound(b.begin(), b.end(), c[i]) - b.begin();
        m = b.size() - 1;
    }
    dfs(1);
    for (ll i = 1; i <= n; i++)
    {
        if (!ok[i])
        {
            ans.push_back(0);
            continue;
        }
        if (g[i].size() <= 1) ans.push_back(1);
        else 
        {
            ll cnt = 0;
            for (ll to : g[i]) cnt += g[to].size() > 0;
            if (cnt > 1)
                ans.push_back(0);
            else if (cnt == 0)
                ans.push_back(1);
            else
            {
                for (ll to : g[i]) if (g[to].size())
                {
                    set<ll> s, s1;
                    for (ll to : g[i]) s.insert(c[to]);
                    for (ll x : g[to]) s1.insert(c[x]);
                    bool ok = true;
                    for (ll i : s1) ok &= s.count(i);
                    ok &= g[to].size() + 1 == sub[to];
                    ans.push_back(ok);
                }
            }
        }
    }
    return ans;
}

• 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