Submission #1008817

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008817		aaaaaarroz	Beech Tree (IOI23_beechtree)	C++17	9 / 100	2101 ms	19444 KiB

beechtree

#include <bits/stdc++.h>
using namespace std;
vector<int> padre;
bool menor_padre(int i, int j){
    return padre[i] < padre[j];
}
vector<int> beechtree(int n, int m, vector<int>P, vector<int>C){
    if(n<9){
        vector<vector<int>>graph(n,vector<int>());
        for(int i=1;i<n;i++){
            graph[P[i]].push_back(i);
        }
        vector<int>ans(n,0);
        for(int i=0;i<n;i++){
            vector<int>sub;
            queue<int>cola;
            cola.push(i);
            while(!cola.empty()){
                int nodo=cola.front(); 
                cola.pop();
                sub.push_back(nodo);
                for(int vecino:graph[nodo]){
                    cola.push(vecino);
                } 
            }
            sort(sub.begin()+1,sub.end());
            if(sub.size()==1){
                ans[i]=1;
                continue;
            }
            do{
                bool bien=true;
                map<int,int>repeticiones;
                for(int j=1;j<sub.size();j++){
                    if(repeticiones.find(C[sub[j]])==repeticiones.end()){
                        repeticiones[C[sub[j]]]=0;
                    }
                    if(sub[repeticiones[C[sub[j]]]]!=P[sub[j]]){
                        bien=false;
                        break;
                    }
                    repeticiones[C[sub[j]]]++;
                }
                if(bien){
                    ans[i]=1;
                    break;
                }
            }while(next_permutation(sub.begin()+1,sub.end()));
        }
        return {ans};
    }
    else{
        vector<vector<int>> graph(n,vector<int>());
        padre = P;
        for(int i = 1; i < n; i++){
            graph[P[i]].push_back(i);
        }
        vector<int> ans(n, 0);
        for(int i = 0; i < n; i++){
            vector<int> sub;
            queue<int> cola;
            cola.push(i);
            while(!cola.empty()){
                int nodo = cola.front(); 
                cola.pop();
                sub.push_back(nodo);
                for(int vecino : graph[nodo]){
                    cola.push(vecino);
                } 
            }
            if(sub.size() == 1){
                ans[i] = 1;  
                continue;
            }
            sort(sub.begin() + 1, sub.end(), menor_padre);  
            bool bien = true;
            map<int, int> repeticiones;
            for(int j = 1; j < sub.size(); j++){
                int color = C[sub[j]];
                if(repeticiones.find(color) == repeticiones.end()){
                    repeticiones[color] = 0;
                }
                int expected_parent = sub[repeticiones[color]]; 
                if(P[sub[j]] != expected_parent){
                    bien = false;
                    break;
                }
                repeticiones[color]++;
            }
            if(bien){
                ans[i] = 1;
            }
        }
        return ans;
    }
}

Compilation message (stderr)

beechtree.cpp: In function 'std::vector<int> beechtree(int, int, std::vector<int>, std::vector<int>)':
beechtree.cpp:34:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |                 for(int j=1;j<sub.size();j++){
      |                             ~^~~~~~~~~~~
beechtree.cpp:78:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |             for(int j = 1; j < sub.size(); j++){
      |                            ~~^~~~~~~~~~~~

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