Submission #1210267

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210267		Nelt	Beech Tree (IOI23_beechtree)	C++20	0 / 100	0 ms	324 KiB

beechtree

#include "beechtree.h"
#include <bits/stdc++.h>
#define endl "\n"
#define ll long long
using namespace std;
vector<int> beechtree(int n, int m, vector<int> P, vector<int> C) {
    vector<vector<pair<int,int>>> adj(n+1);
    set<int> colors;
    for(int i=0;i<n-1;i++){
        int u = P[i]+1, v = i+2, col = C[i];
        adj[u].push_back({v, col});
        adj[v].push_back({u, col});
        colors.insert(col);
    }
    int root = 1;
    vector<int> parent(n+1), pcol(n+1);
    vector<vector<pair<int,int>>> children(n+1);
    function<void(int,int,int)> dfs1 = [&](int x, int p, int col){
        parent[x] = p;
        pcol[x] = col;
        for(auto &pr : adj[x]){
            int y = pr.first, col_e = pr.second;
            if(y==p) continue;
            children[x].push_back({y, col_e});
            dfs1(y, x, col_e);
        }
    };
    dfs1(root, 0, 0);

    vector<ll> subsize(n+1);
    vector<unordered_map<int,ll>> childSize(n+1);
    bool ok = true;
    function<void(int)> dfs2 = [&](int x){
        subsize[x] = 1;
        unordered_map<int,int> seen;
        for(auto &pr : children[x]){
            int y = pr.first, col = pr.second;
            dfs2(y);
            if(++seen[col] > 1) ok = false;
            childSize[x][col] = subsize[y];
            subsize[x] += subsize[y];
        }
    };
    dfs2(root);
    if(!ok) return {};

    for(int col : colors){
        ll smin = LLONG_MAX;
        for(int i=1;i<=n;i++){
            auto it = childSize[i].find(col);
            if(it!=childSize[i].end()) smin = min(smin, subsize[i]);
        }
        if(smin==LLONG_MAX) continue;
        for(int i=1;i<=n;i++){
            if(subsize[i] >= smin && childSize[i].count(col)==0){ ok = false; break; }
        }
        if(!ok) break;
        vector<pair<ll,ll>> vec;
        for(int i=1;i<=n;i++){
            auto it = childSize[i].find(col);
            ll z = (it==childSize[i].end()?0:it->second);
            vec.push_back({subsize[i], z});
        }
        sort(vec.begin(), vec.end());
        ll last = -1;
        for(auto &pr : vec){ if(pr.second < last){ ok=false; break;} last=pr.second; }
        if(!ok) break;
    }
    if(!ok) return {};

    priority_queue<pair<ll,int>> pq;
    pq.push({subsize[root], root});
    vector<int> order;
    order.reserve(n);
    while(!pq.empty()){
        auto [sz, x] = pq.top(); pq.pop();
        order.push_back(x);
        for(auto &pr : children[x]){
            pq.push({subsize[pr.first], pr.first});
        }
    }
    reverse(order.begin(), order.end());
    vector<int> res(n);
    for(int i=0;i<n;i++) res[order[i]-1] = i;
    return res;
}

• 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