Submission #1205488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205488		PagodePaiva	Beech Tree (IOI23_beechtree)	C++20	0 / 100	3 ms	7240 KiB

beechtree

#include "beechtree.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 300010;

vector <int> g[N];
int res[N];

vector<int> beechtree(int n, int m, std::vector<int> p, std::vector<int> c){
    for(int i = 1;i < n;i++){
        g[p[i]].push_back(i);
        g[i].push_back(p[i]);
    }    
    for(int i = 1;i < n;i++){
        set <int> s;
        if(p[i] != 0){
            res[i] = 1;
        }
        else{
            int v = i;
            for(auto x : g[v]){
                if(x == 0)
                    continue;
                s.insert(c[x]);
            }
            int tam = g[v].size();
            if(tam-1 == s.size())
                res[i] = 1;
            else
                res[i] = 0;
        }
    }
    res[0] = 1;
    vector <pair <int, int>> comp;
    for(int i = 1;i < n;i++){
        if(res[i] == 0){
            res[0] = 0;
        }
        if(p[i] == 0){
            int v = i;
            int tam = g[v].size();
            tam--;
            comp.push_back({tam, v});
        }
    }
    sort(comp.begin(), comp.end());
    comp.push_back({g[0].size(), 0});
    set <int> vertices;
    for(auto [tam, v] : comp){
        //cout << tam << ' ' << v << '\n';
        int cnt = 0;
        for(auto x : g[v]){
            if(x == 0)
                continue;
            if(vertices.find(c[x]) != vertices.end())
                cnt++;
        }
        if(cnt != vertices.size()){
            res[0] = 0;
            break;
        }
        for(auto x : g[v]){
            if(x == 0)
                continue;
            vertices.insert(c[x]);
        }
    }   
    set <int> aux; 
    for(auto x : g[0]){
        if(aux.find(x) != aux.end()){
            res[0] = 0;
        }
        aux.insert(x);
    }
    vector <int> ans;
    for(int i = 0;i < n;i++){
        ans.push_back(res[i]);
    }
    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