Submission #981078

#	Time	Username	Problem	Language	Result	Execution time	Memory
981078		vjudge1	Beech Tree (IOI23_beechtree)	C++17	14 / 100	2092 ms	11404 KiB

beechtree

#include<bits/stdc++.h>
#define F first
#define S second
#define PB push_back
using namespace std;
const long long MOD=1e9+7, INF=1e18;
const int INFI=1e9;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<pair<int, ii>> viii;
typedef vector<vii> vvii;
typedef vector<ll> vll;
typedef vector<vll> vvll;
void getPerm(vvii &al, vi &perm, int node, int p){
    perm.PB(node);
    for(auto num:al[node])
        if(num.F!=p)    getPerm(al, perm, num.F, node);
}
bool check(vi &perm, vi &p, vi &cnt, vi &c, vi &index, int root){
    if(index[root]!=0)   return false;
    for(int i=1;i<(int)perm.size();i++){
        if(cnt[c[perm[i]]]!=index[p[perm[i]]])    return false;
        cnt[c[perm[i]]]++;
    }
    return true;
}
vi beechtree(int n, int m, vi p, vi c){
    bool line=true;
    for(int i=1;i<n;i++)    if(p[i]!=i-1)   line=false;
    if(line){
        vi ans(n, 0);
            set<int> cnt;
            for(int i=n-1;i>=0;i--){
                if(cnt.size()<=1)   ans[i]=1;
                cnt.insert(c[i]);
            }
            return ans;
    }
    vi ans(n, 0);
    vvii al(n, vii());
    for(int i=0;i<n;i++)
        if(i!=0)    al[p[i]].PB({i, c[i]});
    for(int i=0;i<n;i++){
        if(al[i].size()==0){
            ans[i]=1;
            continue;
        }
        vi perm, cnt(m+1, 0), index(n);
        getPerm(al, perm, i, p[i]);
        sort(perm.begin(), perm.end());
        do{
            for(int j=0;j<perm.size();j++)    index[perm[j]]=j;
            for(int j=0;j<=m;j++)   cnt[j]=0;
            if(check(perm, p, cnt, c, index, i))    ans[i]=1;
        }while(next_permutation(perm.begin(), perm.end()));
    }
    return ans;
}

Compilation message (stderr)

beechtree.cpp: In function 'vi beechtree(int, int, vi, vi)':
beechtree.cpp:55:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |             for(int j=0;j<perm.size();j++)    index[perm[j]]=j;
      |                         ~^~~~~~~~~~~~

• 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