제출 #1208241

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1208241		ml_tss	Bosses (BOI16_bosses)	C++20	0 / 100	0 ms	320 KiB

bosses

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

const int INF = 1e9;
int n;
vector<vector<int>> accepts;
vector<bool> used;
vector<vector<int>> tree;
int best_cost = INF;

int dfs(int u) {
    if (tree[u].empty()) return 1;
    int sum = 0;
    for (int v : tree[u]) {
        sum += dfs(v);
    }
    return sum + 1;
}

void build_tree(int placed, int root) {
    if (placed == n) {
        int cost = dfs(root);
        best_cost = min(best_cost, cost);
        return;
    }

    for (int i = 0; i < n; i++) {
        if (used[i]) continue;
        for (int j = 0; j < n; j++) {
            if (!used[j]) continue;
            if (find(accepts[i].begin(), accepts[i].end(), j) != accepts[i].end()) {
                used[i] = true;
                tree[j].push_back(i);
                build_tree(placed + 1, root);
                tree[j].pop_back();
                used[i] = false;
            }
        }
    }
}

int main() {
    cin >> n;
    accepts.resize(n);
    used.assign(n, false);
    tree.resize(n);

    for (int i = 0; i < n; i++) {
        int k;
        cin >> k;
        accepts[i].resize(k);
        for (int j = 0; j < k; j++) {
            cin >> accepts[i][j];
            accepts[i][j]--;
        }
    }

    // Essayer chaque nœud comme racine
    for (int r = 0; r < n; r++) {
        bool valid_root = true;
        for (int i = 0; i < n; i++) {
            if (i == r) continue;
            if (find(accepts[i].begin(), accepts[i].end(), r) == accepts[i].end()) {
                valid_root = false;
                break;
            }
        }
        if (!valid_root) continue;

        fill(used.begin(), used.end(), false);
        for (auto& v : tree) v.clear();

        used[r] = true;
        build_tree(1, r);
    }

    cout << best_cost << endl;
}

• Subtask 1: 0 / 22
• Subtask 2: 0 / 45
• Subtask 3: 0 / 33