Submission #1245426

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245426		Pekiban	Beech Tree (IOI23_beechtree)	C++20	58 / 100	2098 ms	58436 KiB

beechtree

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

using namespace std;
using ll = long long;
#define pb push_back

mt19937_64 rng(time(0));
const int N = 2e5 + 5;
bool ok[N];
vector<array<int, 2>> ch[N];
ll cl[N];
int sz[N], c[N];
void dfs(int s) {
    set<int> st;
    ok[s] = 1, sz[s] = 1; 
    for (auto [u, w] : ch[s]) {
        if (st.count(w)) ok[s] = 0;
        st.insert(w);
        dfs(u);
        sz[s] += sz[u], ok[s] &= ok[u];
    }
}
void dfscnt(int s, map<int, int> &f) {
    for (auto [u, w] : ch[s]) {
        f[w]++;
        dfscnt(u, f);
    }
}
bool chk(int s) {
    map<int, int> f;
    ll h[sz[s]];
    fill(h, h+sz[s], 0);
    dfscnt(s, f);
    for (auto [x, y] : f) {
        // if (s == 0) cout << x << 'z' << y << endl;
        for (int i = 0; i < y; ++i) h[i] ^= cl[x];
    }
    map<int, int> t, t2, t3;
    set<array<ll, 4>> st;
    ll xx = 0;
    for (auto [u, w] : ch[s]) {
        xx ^= cl[w];
        // if (s == 0) cout << w << '|';
        ll x = 0;
        for (auto [v, W] : ch[u])   x ^= cl[W];
        t[u] = t2[w];
        t2[w]++;
        st.insert({x, -sz[u], t[u], u});
    }
    // if (s == 0) cout << xx << ' ' << h[0] << endl;
    if (xx != h[0]) return 0;
    // if (s == 2) {
    //     for (auto [p, q, r, t] : st)  cout << p << ' ' << q << ' ' << r << '\n';
    //     cout << h[1] << 't' << h[2] << '\n';
    //     for (auto [x, y] : f) {
    //         cout << x << " " << y << '\n';
    //     }
        
    // }
    for (int i = 1; i < sz[s]; ++i) {
        auto it = st.lower_bound({h[i], (int)-1e9, 0, 0});
        if ((*it)[0] != h[i])    return 0;
        int x = (*it)[3];
        it = st.erase(it);
        // if (s == 2)   cout << x << ' ' << t[x] << ' ' << ' ' << t3[c[x]] << '\n';
        if (t[x] != t3[c[x]])   return 0;
        t3[c[x]]++;
        for (auto [u, w] : ch[x]) {
            ll xx = 0;
            for (auto [v, W] : ch[u])   xx ^= cl[W];
            t[u] = t2[c[u]];
            t2[c[u]]++;
            // if (s == 4) cout << xx << 'z' << u << '\n';
            st.insert({xx, -sz[u], t[u], u});
        }
    }
    return 1;
}
vector<int> beechtree(int n, int m, vector<int> P, vector<int> C) {
    for (int i = 1; i < n; ++i) ch[P[i]].pb({i, C[i]});
    for (int i = 1; i <= m; ++i) cl[i] = rng() % (1LL << 62);
    for (int i = 1; i < n; ++i) c[i] = C[i];
    dfs(0);
    vector<int> ans(n);
    for (int i = 0; i < n; ++i) ans[i] = (ok[i] ? chk(i) : 0);
    return ans;
}

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