Submission #1218387

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218387		vanea	Beech Tree (IOI23_beechtree)	C++20	0 / 100	110 ms	104520 KiB

beechtree

#include <bits/stdc++.h>
#include "beechtree.h"
using namespace std;
using ll = long long;

const int mxN = 2e5+10;

int c[mxN], dep[mxN], sz[mxN];
vector<int> adj[mxN];
bool pos[mxN];
array<int, 2> cont[mxN];

set<int> dfs(int node, int p) {
    set<int> colors, all_colors;
    int cont_cnt = 0, cont_mx = 0;
    sz[node] = 1;
    vector<set<int>> v;
    for(auto it : adj[node]) {
        if(it == p) continue;
        if(colors.count(c[it]) != 0) {
            pos[node] = false; break;
        }
        all_colors.insert(c[it]);
        colors.insert(c[it]);
        set<int> nxt_colors = dfs(it, node);
        sz[node] += sz[it];
        dep[node] = max(dep[node], dep[it]+1);
        if(!pos[it]) {
            pos[node] = false; break;
        }
        v.push_back(nxt_colors);
        if(cont[it][0] >= 2) {
            ++cont_cnt;
            cont_mx = max(cont_mx, cont[it][0]);
            if(cont[it][1] != c[it]) pos[node] = false;
        }
        if(nxt_colors.size() > all_colors.size()) swap(nxt_colors, all_colors);
        for(auto it : nxt_colors) {
            all_colors.insert(it);
        }
    }
    if(cont_cnt > 1) {
        pos[node] = false;
    }
    for(auto it : all_colors) {
        if(!colors.count(it)) {
            pos[node] = false; break;
        }
    }
    if(dep[node] > 2) pos[node] = false;
    if(cont_cnt == 1) {
        if(sz[node] == (cont_mx + adj[node].size())) return all_colors;
        pos[node] = false;
        return {};
    }
    if(!pos[node]) return {};
    for(auto it : adj[node]) {
        if(it == p) continue;
        if(cont[it][0] + 1 > cont[node][0]) {
            if(cont[it][1] == c[it]) {
                cont[node][0] = cont[it][0] + 1;
                cont[node][1] = c[it];
            }
        }
        if(cont[node][0] == 0) {
            cont[node][0] = 1;
            cont[node][1] = c[it];
        }
    }
    sort(v.begin(), v.end(), [&](set<int> a, set<int> b) {
        return a.size() > b.size();
    });
    for(int i = 1; i < v.size(); i++) {
        for(auto it : v[i]) {
            int it1 = v[i-1].count(it);
            if(it1 == 0) {
                pos[node] = false;
                break;
            }
        }
    }
    if(pos[node]) return all_colors;
    else return {};
}

vector<int> beechtree(int n, int m, vector<int> p, vector<int> C) {
    for(int i = 1; i < n; i++) {
        adj[i].push_back(p[i]);
        adj[p[i]].push_back(i);
        c[i] = C[i];
        pos[i] = true;
    }
    adj[0].push_back(-1);
    pos[0] = true;
    dfs(0, -1);
    vector<int> ans(n);
    for(int i = 0; i < n; i++) ans[i] = pos[i];
    return ans;
}


/*int main()
{
    vector<int> ans = beechtree(18, 3,
 {-1, 0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 5, 10, 11, 11},
 {0, 1, 2, 3, 1, 2, 3, 1, 3, 3, 2, 1, 1, 2, 2, 1, 2, 3});
    for(auto it : ans) {
        cout << it << ' ';
    }
}*/

• 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