Submission #842198

#	Time	Username	Problem	Language	Result	Execution time	Memory
842198		gs18115	Beech Tree (IOI23_beechtree)	C++17	100 / 100	1010 ms	95948 KiB

beechtree

#include"beechtree.h"
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
const int mxn=200010;
vector<pi>adj[mxn];
int sz[mxn];
void dfs(int x)
{
    sz[x]=1;
    for(pi&t:adj[x])
        dfs(t.fi),sz[x]+=sz[t.fi];
    return;
}
bool isinc(const vector<int>&x,const vector<int>&y)
{
    if(x.size()>y.size())
        return 0;
    for(const int&t:x)
        if(!binary_search(all(y),t))
            return 0;
    return 1;
}
vector<int>subtr[mxn];
multimap<int,int>ss[mxn];
map<int,set<pi> >mm[mxn];
int n,m;
int p[mxn],c[mxn];
vector<vector<int> >st;
bool push(int i,int j)
{
    subtr[i].eb(j);
    int x=sz[j];
    auto&s=ss[i];
    {
        auto it=s.ep(x,j);
        if(it!=s.begin())
        {
            auto it2=prev(it);
            if(!isinc(st[it2->se],st[j]))
                return 0;
        }
        auto it2=next(it);
        if(it2!=s.end())
        {
            if(!isinc(st[j],st[it2->se]))
                return 0;
        }
    }
    if(j==0)
        return 1;
    set<pi>&m=mm[i][c[j]];
    int y=sz[p[j]];
    {
        auto it=m.ep(x,y).fi;
        if(it!=m.begin())
        {
            auto it2=prev(it);
            if(it2->se>y||(x!=it2->fi&&y==it2->se))
                return 0;
        }
        auto it2=next(it);
        if(it2!=m.end())
        {
            if(y>it2->se||(x!=it2->fi&&y==it2->se))
                return 0;
        }
    }
    return 1;
}
vector<int>beechtree(int N,int M,vector<int>P,vector<int>C)
{
    n=N,m=M;
    for(int i=0;i<n;i++)
        p[i]=P[i],c[i]=C[i];
    vector<int>isok(n,1);
    for(int i=1;i<n;i++)
        adj[p[i]].eb(i,c[i]);
    st.resize(n);
    for(int i=n;i-->0;)
    {
        for(pi&t:adj[i])
            st[i].eb(t.se);
        sort(all(st[i]));
        auto it=unique(all(st[i]));
        if(it!=st[i].end())
            isok[i]=0;
        if(isok[i]==0&&i>0)
            isok[p[i]]=0;
        st[i].eb(inf);
    }
    dfs(0);
    vector<int>vv;
    for(int i=0;i<n;i++)
        if(isok[i]==1)
            vv.eb(i);
    sort(all(vv),[&](int x,int y){return sz[x]<sz[y];});
    for(int&i:vv)
    {
        if(isok[i]==0)
        {
            if(i>0)
                isok[p[i]]=0;
            continue;
        }
        for(pi&tt:adj[i])
        {
            int t=tt.fi;
        }
        push(i,i);
        for(pi&tt:adj[i])
        {
            int t=tt.fi;
            if(subtr[t].size()>subtr[i].size())
                swap(subtr[t],subtr[i]),
                swap(ss[t],ss[i]),
                swap(mm[t],mm[i]);
            ss[t].clear();
            mm[t].clear();
            for(int&x:subtr[t])
            {
                if(!push(i,x))
                {
                    isok[i]=0;
                    break;
                }
            }
            subtr[t].clear();
            if(isok[i]==0)
                break;
        }
        if(isok[i]==0)
        {
            if(i>0)
                isok[p[i]]=0;
            continue;
        }
    }
    return isok;
}

Compilation message (stderr)

beechtree.cpp: In function 'std::vector<int> beechtree(int, int, std::vector<int>, std::vector<int>)':
beechtree.cpp:121:17: warning: unused variable 't' [-Wunused-variable]
  121 |             int t=tt.fi;
      |                 ^

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