제출 #1245367

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1245367		Pekiban	참나무 (IOI23_beechtree)	C++20	9 / 100	2096 ms	25528 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<array<ll, 3>> st;
    for (auto [u, w] : ch[s]) {
        ll x = 0;
        for (auto [v, W] : ch[u])   x ^= cl[W];
        t[u] = t2[w];
        t2[w]++;
        st.insert({x, t[u], u});
    }
    // 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, 0});
        if ((*it)[0] != h[i])    return 0;
        int x = (*it)[2];
        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, t[u], u});
        }
    }
    return 1;
}
void dfst(int s, vector<int> &v) {
    v.pb(s);
    for (auto [u, w] : ch[s]) {
        dfst(u, v);
    }
}
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]});
    vector<int> ans(n);
    for (int i = 0; i < n; ++i) {
        vector<int> v;
        dfst(i, v);
        int t[m+1];
        fill(t, t+m+1, 0);
        // cout << i << endl;
        ans[i] = 0;
        do {
            bool ok = 1;
            if (v[0] != i)  continue;
            vector<int> d;
            for (auto x : v) {
                if (x == i) continue;
                if (P[x] != v[t[C[x]]]) {
                    ok = 0;
                    break;
                }
                t[C[x]]++;
                d.pb(C[x]);
            }
            for (auto x : d)    t[x] = 0;
            ans[i] |= ok;
        }   while(next_permutation(v.begin(), v.end()));
    }
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 9 / 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