Submission #1205941

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205941		PagodePaiva	Beech Tree (IOI23_beechtree)	C++20	8 / 100	91 ms	38840 KiB

beechtree

#include "beechtree.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 300010;

vector <int> g[N];
int res[N];
int h[N];
vector <int> c;
vector <int> p;

void solve(int v){
    if(h[v] == 0){
        res[v] = 1;
    }
    if(h[v] == 1){
        set <int> s;
        int i = v;
        for(auto x : g[v]){
            if(x == p[v])
                continue;
            s.insert(c[x]);
        }
        int tam = g[v].size();
        if(tam-(p[v] == -1 ? 0 : 1) == s.size())
            res[i] = 1;
        else
            res[i] = 0;
    }
    if(h[v] == 2){
        res[v] = 1;
        int cnt = 0;
        for(auto x : g[v]){
            if(x == p[v]){
                continue;
            }
            if(g[x].size() > 1)
                cnt++;
        }
        if(cnt > 1){
            res[v] = 0;
            return;
        }
        set <int> s;
        int t = -1;
        for(auto x : g[v]){
            if(x == p[v])
                continue;
            if(s.find(c[x]) != s.end()){
                res[v] = 0;
                return;
            }
            s.insert(c[x]);
            if(g[x].size() > 1){
                t = x;
            }
        }
        for(auto x : g[t]){
            if(x == p[t])
                continue;
            if(s.find(c[x]) == s.end()){
                res[v] = 0;
                return;
            }
        }
        return;
    }
    if(h[v] > 2){
        res[v] = 0;
    }
}

vector <pair <int, int>> ord;

void dfs(int v, int p){
    h[v] = 0;
    for(auto x : g[v]){
        if(x == p)
            continue;
        dfs(x, v);
        h[v] = max(h[v], h[x]+1);
    }
    return;
}

vector<int> beechtree(int n, int m, std::vector<int> pp, std::vector<int> cc){
    c = cc;
    p = pp;
    for(int i = 1;i < n;i++){
        g[p[i]].push_back(i);
        g[i].push_back(p[i]);
    }    
    dfs(0, 0);
    for(int i = 0;i < n;i++){
        ord.push_back({h[i], i});
    }
    sort(ord.begin(), ord.end());
    for(auto [hh, v] : ord){
        solve(v);
    }
    vector <int> ans;
    for(int i = 0;i < n;i++){
        ans.push_back(res[i]);
    }
    return ans;
}

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