Submission #856175

#	Time	Username	Problem	Language	Result	Execution time	Memory
856175		Sorting	Beech Tree (IOI23_beechtree)	C++17	9 / 100	2083 ms	47528 KiB

beechtree

#include "beechtree.h"
#include <algorithm>
#include <map>

using namespace std;

const int N = 2e5 + 3;

int n, m, c[N], p[N];
vector<int> adj[N];

vector<int> get_subtree(int x){
    vector<int> subtree{x};
    for(int to: adj[x]){
        vector<int> add = get_subtree(to);
        for(int y: add){
            subtree.push_back(y);
        }
    }
    return subtree;
}

bool check(vector<int> &subtree){
    map<int, int> cnt;
    for(int i = 1; i < subtree.size(); ++i){
        int node = subtree[i];
        int color = c[node];

        if(p[node] != subtree[cnt[color]]){
            return false;
        }
        ++cnt[color];
    }
    return true;
}

std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C)
{
    n = N, m = M;
    copy(C.begin(), C.end(), c);
    copy(P.begin(), P.end(), p);
    for(int i = 1; i < n; ++i){
        adj[P[i]].push_back(i);
    }

    vector<int> ans;
    for(int i = 0; i < n; ++i){
        vector<int> subtree = get_subtree(i);
        sort(subtree.begin(), subtree.end());

        bool ok = false;
        do{
            if(subtree[0] != i){
                continue;
            }

            if(check(subtree)){
                ok = true;
                break;
            }
        }
        while(next_permutation(subtree.begin(), subtree.end()));

        ans.push_back(ok);
    }
    return ans;
}

Compilation message (stderr)

beechtree.cpp: In function 'bool check(std::vector<int>&)':
beechtree.cpp:25:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(int i = 1; i < subtree.size(); ++i){
      |                    ~~^~~~~~~~~~~~~~~~

• 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