제출 #1327636

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1327636		SpyrosAliv	Beech Tree (IOI23_beechtree)	C++20	17 / 100	85 ms	26780 KiB

beechtree

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

int n, m;
vector<int> p, c, maxPath;
vector<vector<int>> tree;

bool superset(set<int> A, set<int> B) {
    for (auto x: B) {
        if (A.find(x) == A.end()) return false;
    }
    return true;
}

void dfs1(int node) {
    maxPath[node] = 1;
    for (auto next: tree[node]) {
        dfs1(next);
        maxPath[node] = max(maxPath[node], maxPath[next] + 1);
    }
}

bool ok(int node) {
    if (maxPath[node] > 3) return false;
    if (maxPath[node] == 1) return true;
    if (maxPath[node] == 2) {
        set<int> cols;
        for (auto next: tree[node]) {
            cols.insert(c[next]);
        }
        if (cols.size() != tree[node].size()) {
            return false;
        }
        else return true;
    }
    else if (maxPath[node] == 3) {
        set<int> cols;
        for (auto next: tree[node]) {
            cols.insert(c[next]);
        }
        if (cols.size() != tree[node].size()) {
            return false;
        }
        vector<pair<int, set<int>>> cands;
        for (auto next: tree[node]) {
            set<int> colsNext;
            for (auto next2: tree[next]) {
                colsNext.insert(c[next2]);
            }
            cands.push_back({colsNext.size(), colsNext});
        }
        sort(cands.rbegin(), cands.rend());
        set<int> curr = cols;
        for (auto [sz, nxt]: cands) {
            if (!superset(curr, nxt)) {
                return false;
            }
            curr = nxt;
        }
        return true;
    }
}

vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C) {
    n = N;
    m = M;
    p = P;
    c = C;
    tree.resize(n);
    maxPath.assign(n, 0);
    for (int i = 1; i < n; i++) {
        tree[p[i]].push_back(i);
    }
    dfs1(0);
    vector<int> ans(n, 0);
    for (int i = 0; i < n; i++) {
        ans[i] = ok(i);
    }
    return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

beechtree.cpp: In function 'bool ok(int)':
beechtree.cpp:63:1: warning: control reaches end of non-void function [-Wreturn-type]
   63 | }
      | ^

• Subtask 0: 0 / 0
• Subtask 1: 0 / 9
• Subtask 2: 0 / 5
• Subtask 3: 9 / 9
• Subtask 4: 8 / 8
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 12
• Subtask 8: 0 / 17
• Subtask 9: 0 / 12