Submission #847653

#	Time	Username	Problem	Language	Result	Execution time	Memory
847653		vjudge1	참나무 (IOI23_beechtree)	C++17	9 / 100	2055 ms	30916 KiB

beechtree

#include "beechtree.h"

#include <bits/stdc++.h>
using namespace std;

std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C) {
        vector<vector<int>> adj(N);
        for (int i = 1; i < N; i++) {
                adj[P[i]].emplace_back(i);
                C[i]--;
        }
        vector<int> f(N);
        function<void(int)> solve = [&](int u) {
                vector<int> node;
                function<void(int)> dfs = [&](int a) {
                        node.emplace_back(a);
                        for (int b : adj[a]) dfs(b);
                };
                dfs(u);
                node.erase(node.begin());
                vector<int> perm(node.size());
                iota(perm.begin(), perm.end(), 1);
                vector<int> cnt(M);
                do {
                        vector<int> num(N, -1);
                        num[u] = 0;
                        for (int i = 0; i < node.size(); i++) num[node[i]] = perm[i];
                        sort(node.begin(), node.end(), [&](int i, int j) {
                                return num[i] < num[j];
                        });
                        bool ok = 1;
                        for (int i : node) {
                                if (num[P[i]] != cnt[C[i]]++) ok = 0;
                        }
                        for (int i : node) cnt[C[i]]--;
                        f[u] |= ok;
                } while (next_permutation(perm.begin(), perm.end()));
                for (int v : adj[u]) solve(v);
        };
        solve(0);
        return f;
}

Compilation message (stderr)

beechtree.cpp: In lambda function:
beechtree.cpp:27:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |                         for (int i = 0; i < node.size(); i++) num[node[i]] = perm[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