Submission #1245325

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245325		Pekiban	참나무 (IOI23_beechtree)	C++20	0 / 100	2098 ms	58440 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) {
        for (int i = 0; i < y; ++i) h[i] ^= cl[x];
    }
    map<int, int> t, t2, t3;
    set<pair<ll, int>> st;
    for (auto [u, w] : ch[s]) {
        ll x = 0;
        for (auto [v, W] : ch[u])   x ^= cl[W];
        st.insert({x, u});
        t[u] = t2[w];
        t2[w]++;
    }
    // if (s == 4) {
    //     for (auto [p, q] : st)  cout << p << ' ' << q << '\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], 0});
        if ((*it).first != h[i])    return 0;
        int x = (*it).second;
        it = st.erase(it);
        // if (s == 4 && i == 2)   cout << 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, 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: 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