Submission #1233938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233938		Sir_Ahmed_Imran	Beech Tree (IOI23_beechtree)	C++17	0 / 100	27 ms	10564 KiB

beechtree

#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 2001
#define nl '\n'
#define ff first
#define ss second
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define add insert
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()

int dept[MAXN];
int x[MAXN][MAXN];
int s[MAXN][MAXN];
vector<int> d[MAXN];
vector<int> a[MAXN];

vector<int> beechtree(int n, int m, vector<int> p, vector<int> c){
    vector<int> ans(n, 1);
    vector<pii> vec;
    for(int i = 1; i < n; i++){
        dept[i] = dept[p[i]] + 1;
        d[dept[i]].append(i);
        a[p[i]].append(i);
    }
    d[0].append(0);
    bool b;
    int v, u;
    for(int h = dept[n - 1]; h >= 0; h--){
        for(int i = 0; i < d[h].size(); i++){
            v = d[h][i];
            vec.clear();
            for(auto & j : a[v]){
                if(x[v][c[j]]) ans[v] = 0;
                x[v][c[j]] = j; 
                vec.append({a[j].size(), j});
            }
            if(!ans[v]) continue;
            sort(all(vec));
            for(int j = 1; j < a[v].size(); j++)
                ans[v] &= s[vec[j].ss][vec[j - 1].ss];
            if(!a[v].empty()){
                for(auto & j : a[vec.back().ss])
                    ans[v] &= (x[v][c[j]] > 0);
            }
            if(!ans[v]) continue;
            for(int j = 0; j < i; j++){
                v = d[h][i], u = d[h][j];
                if(!ans[u]) continue;
                if(a[v].size() < a[u].size())
                    swap(v, u);
                s[v][u] = 1;
                for(auto & k : a[u]){
                    if(!s[x[v][c[k]]][k])
                        s[v][u] = 0;
                }
                if(a[v].size() == a[u].size())
                    s[u][v] = s[v][u];
            }
        }
    }
    return ans;
}

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