Submission #1339632

#	Time	Username	Problem	Language	Result	Execution time	Memory
1339632		hccoder	Beech Tree (IOI23_beechtree)	C++20	5 / 100	34 ms	5032 KiB

beechtree

#include "bits/stdc++.h"
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
using namespace std;
using ll = long long;

bool is_path(vector<int> P){
    for (int i = 1; i<P.size(); i++){
        if (P[i]!=i-1) return false;
    }
    return true;
}

bool mx_cnt(vector<int> C){
    vector<int> cnt(C.size()+1);
    for (int e: C) cnt[e]++;
    return *max_element(all(cnt))<=2;
}

vector<int> beechtree(int N, int M, vector<int> P, vector<int> C){
    vector<int> R(N);
    if (is_path(P)){
        set<int> st;
        for (int i = N-1; i>=0; i--){
            if (st.size()<=1) R[i] = 1;
            else break;
            st.insert(C[i]);
        }
    }
    else if (mx_cnt(C)){
        vector<vector<int>> g(N);
        for (int i = 1; i<N; i++){
            g[P[i]].push_back(i);
            g[i].push_back(P[i]);
        }
        vector<int> height(N);
        auto dfs = [&] (auto&& self, int u, int p) -> void {
            vector<int> ch;
            int cnt = 0;
            set<int> st;
            for (int e: g[u]){
                if (e!=p){
                    self(self, e, u);
                    height[u] = max(height[u], height[e]+1);
                    if (height[e]==1) ch.push_back(e);
                    st.insert(C[e]);
                    cnt++;
                }
            }
            if (height[u]==0) R[u] = 1;
            else if (height[u]==1){
                if (st.size()==cnt) R[u] = 1;
            }
            else {
                if (st.size()==cnt && ch.size()==1){
                    int v = ch[0];
                    bool f = true;
                    for (int e: g[v]){
                        if (st.find(C[e])==st.end()) f = false;
                    }
                    if (f) R[u] = 1;
                }
            }
        };
        dfs(dfs, 0, 0);
    }
    return R;
}

// int main(){
    
// }

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