Submission #1215858

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215858		ASGA_RedSea	Beech Tree (IOI23_beechtree)	C++20	14 / 100	68 ms	46512 KiB

beechtree

/**

                                    * بسم الله الرحمن الرحيم *

                ﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿

*/

/// author : "ASGA"

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;
using ll=long long;

#include"beechtree.h"


int S=0;
int n,m;
vector<int>c,ans,p;
vector<vector<int>>a;



vector<vector<int>>nd;
void calc1(int i){
    vector<int>&pp=nd[i];

    pp={i};
    for(int&j:a[i]){
        calc1(j);
        for(int&k:nd[j])pp.push_back(k);
    }

    sort(pp.begin(),pp.end());

    ans[i]=0;

    do{
        vector<int>f(m+1,0);
        int vl=1;

        for(int i=1;i<pp.size();i++){
            vl&=pp[f[c[pp[i]]]]==p[pp[i]];
            f[c[pp[i]]]++;
        }

        if(vl){ans[i]=1;break;}
    }
    while(next_permutation(pp.begin()+1,pp.end()));
}

vector<int>d;
void calc2(int i){
    int vv=0;
    for(int&j:a[i]){
        calc2(j);
        d[i]=max(d[j]+1,d[i]);
        vv+=a[j].size()>0;
    }

    ans[i]&=(d[i]<=2&&vv<=1);
}

void check(int i){
    set<int>s;
    for(int&j:a[i]){
        check(j);
        ans[i]&=ans[j];
        s.insert(c[j]);
    }

    ans[i]&=s.size()==a[i].size();
}

vector<int>beechtree(int N,int M,vector<int>P,vector<int>C){
    n=N;m=M;c=C;a.resize(n);ans.assign(n,1);p=P;
    for(int i=1;i<n;i++)a[p[i]].push_back(i);

    check(0);

    S=1;for(int i=1;i<n;i++)S&=p[i]==i-1;

    vector<int>f(m+1,0);for(int&i:c)f[i]++;

    if(n<9){
        nd.resize(n);
        calc1(0);
    }
    else if(S){
        ans[n-1]=1;
        int i;
        for(i=n-1;i>0&&c[i]==c.back();i--)ans[i-1]=1;
        for(;i>0;i--)ans[i-1]=0;
    }
    else if(*max_element(f.begin(),f.end())<3){
        d.assign(n,0);
        calc2(0);
    }
    else{
        ;
    }



    return ans;
}

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