Submission #1205502

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205502		PagodePaiva	Beech Tree (IOI23_beechtree)	C++20	9 / 100	51 ms	16064 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;
        return;
    }
    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-1 == s.size())
            res[i] = 1;
        else
            res[i] = 0;
    }
    if(h[v] == 2){
        res[v] = 1;
        vector <pair <int, int>> comp;
        for(auto i : g[v]){
            if(i == p[v])
                continue;
            if(res[i] == 0){
                res[v] = 0;
            }
            if(p[i] == v){
                int v = i;
                int tam = g[v].size();
                tam--;
                comp.push_back({tam, v});
            }
        }
        sort(comp.begin(), comp.end());
        comp.push_back({g[v].size(), v});
        set <int> vertices;
        for(auto [tam, vv] : comp){
            int cnt = 0;
            for(auto x : g[vv]){
                if(x == v)
                    continue;
                if(vertices.find(c[x]) != vertices.end())
                    cnt++;
            }
            if(cnt != vertices.size()){
                res[v] = 0;
                break;
            }
            for(auto x : g[vv]){
                if(x == v)
                    continue;
                vertices.insert(c[x]);
            }
        }   
        set <int> aux; 
        for(auto x : g[v]){
            if(x == p[v])
                continue;
            if(aux.find(c[x]) != aux.end()){
                res[v] = 0;
            }
            aux.insert(c[x]);
        }
    }
    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: 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