제출 #1290994

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290994		user736482	참나무 (IOI23_beechtree)	C++20	13 / 100	202 ms	100364 KiB

beechtree

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 998244353LL
#define INF 1000000001LL
#define POT (1LL<<20)
#define INFL 1000000000000000099LL
#define pii pair<ll,ll>
#define ppi pair<pii,ll>
#define pip pair<ll,pii>
#define ppp pair<pii,pii>
#define vi vector<ll>
#define vii vector<pii>
#define vvi vector<vi>
#define al(x) x.begin(),x.end()
#define rev(x) reverse(al(x))
#define X 18
template<typename T, typename U>
pair<T, U> operator+(const pair<T, U>& a, const pair<T, U>& b) {
    return {a.first + b.first, a.second + b.second};
}
template<typename T, typename U>
pair<T, U> operator-(const pair<T, U>& a, const pair<T, U>& b) {
    return {a.first - b.first, a.second - b.second};
}
template<typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    os<<"{"<<p.ff<<", "<<p.ss<<"}";
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "{";
    for (size_t i = 0; i < v.size(); ++i) {
        if (i) os << ", ";
        os << v[i];
    }
    os << "}";
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, const set<T>& v) {
    os << "{";
    for (auto i=v.begin(); i != v.end(); ++i) {
        if (i!=v.begin()) os << ", ";
        os << *i;
    }
    os << "}";
    return os;
}
ll fct[1000007];
ll fp(ll a,ll b){
    ll c=1;while(b){if(b&1)c=(c*a)%MOD;a=(a*a)%MOD;b/=2;}
    return c;
}
ll iv(ll a){
    return fp(a,MOD-2);
}
ll bnm(ll a,ll b){
    if(b>a || a<0)return 0;
    return ((fct[a]*iv(fct[b]))%MOD*iv(fct[a-b]))%MOD;
}
set<ll>s[200007];
set<pii>s2[200007];
vi d[200007];
bool zl[200007];
bool cz(ll a,ll b){
    for(ll i:s[a]){
        if(s[b].find(i)==s[b].end())return 0;
    }
    return 1;
}
void dfs(ll v){
    s2[v].insert({s[v].size(),v});
    for(ll i : d[v]){
        dfs(i);
        zl[v]|=zl[i];
        if(s2[i].size()>s2[v].size())swap(s2[i],s2[v]);
        for(pii j : s2[i]){
            s2[v].insert(j);
            auto it=s2[v].lower_bound(j);
            if(it!=s2[v].begin()){
                if(!cz((*--it).ss,j.ss)){
                    zl[v]=1;
                    
                }
                it++;
            }
            it++;
            if(it!=s2[v].end())if(!cz(j.ss,(*it).ss))zl[v]=1;
        }
    }
}
vector<int>beechtree(int n,int m,vector<int>p,vector<int>c){
    for(ll i=1;i<n;i++){
        d[p[i]].pb(i);
    }
    for(ll i=0;i<n;i++){
        for(ll j : d[i]){
            if(s[i].find(c[j])!=s[i].end())zl[i]=1;
            else s[i].insert(c[j]);
        }
    }
    dfs(0);
    vector<int>ns;
    for(ll i=0;i<n;i++)ns.pb(!zl[i]);
    return ns;
}

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