Submission #1069664

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069664		Malix	Beech Tree (IOI23_beechtree)	C++17	23 / 100	2079 ms	13960 KiB

beechtree

#include "beechtree.h"
#include<bits/stdc++.h>
using namespace std;
 
#define REP(a,b,c) for(int a=b;a<c;a++)
#define PB push_back
#define F first
#define S second
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
 
std::vector<int> beechtree(int n, int m, std::vector<int> p, std::vector<int> c)
{
    if(n<=8){
        vi ans(n,0);
        vii a(n);
        REP(i,0,n)a[i].PB(i);
        for(int i=n-1;i>=1;i--)for(auto u:a[i])a[p[i]].PB(u);
        vii b=a;
        REP(i,0,n){
            int s=a[i].size();
            if(s==1){
                ans[i]=1;
                continue;
            }
            map<int,int> mp;
            bool flag=1;
            REP(j,1,s){
                if(b[i][mp[c[b[i][j]]]]!=p[b[i][j]]){
                    flag=0;
                    break;
                }
                mp[c[b[i][j]]]++;
            }
            if(flag){
                ans[i]=1;
                continue;
            }
            next_permutation(b[i].begin()+1,b[i].end());
            while(b[i]!=a[i]){
                mp.clear();
                flag=1;
                REP(j,1,s){
                    if(b[i][mp[c[b[i][j]]]]!=p[b[i][j]]){
                        flag=0;
                        break;
                    }
                    mp[c[b[i][j]]]++;
                }
                if(flag)break;
                next_permutation(b[i].begin()+1,b[i].end());
            }
            if(flag)ans[i]=1;
        }
        return ans;
    }
    bool flag=1;
    REP(i,1,n)if(p[i]!=i-1)flag=0;
    if(flag){
        vi ans(n,0);
        ans[n-1]=1;
        ans[n-2]=1;
        int k=c[n-1];
        for(int i=n-2;i>=1;i--){
            if(c[i]!=k)break;
            ans[p[i]]=1;
        }
        return ans;
    }
    flag=1;
    REP(i,1,n)if(p[p[i]]!=0&&p[p[i]]!=-1)flag=0;
    if(flag){
        vi ans(n,-1);
        REP(i,1,n)if(p[i]!=0)ans[i]=1;
        vii a(n);
        REP(i,1,n)a[p[i]].PB(i);
        vii b(n);vector<pi> arr;
        REP(i,0,n)if(p[i]==0||p[i]==-1){
            if(a[i].size()==0)continue;
            set<int> st;
            for(auto u:a[i]){
                if(st.count(c[u])!=0){
                    ans[i]=0;
                    ans[0]=0;
                }
                st.insert(c[u]);
            }
            for(auto u:st)b[i].PB(u);
            int s=b[i].size();
            arr.PB({s,i});
        }
        REP(i,1,n)if(ans[i]==-1)ans[i]=1;
        if(ans[0]==0)return ans;
        sort(arr.begin()+1,arr.end());
        reverse(arr.begin()+1,arr.end());
        int k=arr.size();
        map<int,int> mp;
        REP(i,0,k){
            int x=arr[i].F;
            int y=arr[i].S;
            for(auto u:b[y]){
                if(mp[u]!=i)ans[0]=0;
                mp[u]++;
            }
            if(ans[0]==0)break;
        }
        if(ans[0]==0)return ans;
        ans[0]=1;
        return ans;
    }
    vi ans(n,-1);
    vii a(n);
    REP(i,1,n)a[p[i]].PB(i);
    vi tmp(n,0);
    REP(i,0,n)if(a[i].size()==0){
        ans[i]=1;
        if(i!=0)tmp[p[i]]++;
    }
    vi arr;
    REP(i,0,n)if(tmp[i]==a[i].size())arr.PB(i);
    int s=arr.size();
    vi brr;
    REP(i,0,s){
        set<int> st;
        int pos=arr[i];
        for(auto u:a[pos]){
            if(st.count(c[u])){
                ans[pos]=0;
                if(p[pos]!=-1)ans[p[pos]]=0;
            }
            st.insert(c[u]);
        }
        if(ans[pos]!=0)ans[pos]=1;
        if(p[pos]!=-1)brr.PB(p[pos]);
    }
    int t=brr.size();
    REP(i,0,t){
        set<int> st;
        int pos=brr[i];
        if(ans[pos]==1)continue;
        for(auto u:a[pos]){
            if(st.count(c[u]))ans[pos]=0;
            st.insert(c[u]);
        }
        bool flag=0;
        for(auto u:a[pos]){
            if(ans[pos]==0)break;
            if(a[u].size()!=0){
                if(flag){
                    ans[pos]=0;
                    break;
                }
                flag=1;
                for(auto v:a[u])if(st.count(c[v])==0)ans[pos]=0;
            }
        }
        if(ans[pos]!=0)ans[pos]=1;
    }
    REP(i,0,n)if(ans[i]==-1)ans[i]=0;
    return ans;
}

Compilation message (stderr)

beechtree.cpp: In function 'std::vector<int> beechtree(int, int, std::vector<int>, std::vector<int>)':
beechtree.cpp:102:17: warning: unused variable 'x' [-Wunused-variable]
  102 |             int x=arr[i].F;
      |                 ^
beechtree.cpp:123:24: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |     REP(i,0,n)if(tmp[i]==a[i].size())arr.PB(i);

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