제출 #717677

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
717677		vjudge1	Bosses (BOI16_bosses)	C++17	100 / 100	1496 ms	960 KiB

bosses

#include <bits/stdc++.h>

using namespace std;

vector<int> adj[5010];
vector<int> g[5010];
vector<bool> vis(5010, false);
vector<int> cnt(5010, 0);
int n, res, check;

void dfs(int u) {
    check++;
    for(auto v : g[u]) {
        dfs(v);
        cnt[u] += cnt[v];
    }
    cnt[u]++;
    return;
}

void solve(int s) {
    for(int i = 1; i <= n; i++) {
        g[i].clear(); vis[i] = false; cnt[i] = 0;
    }
    queue<int> q;
    q.push(s);
    vis[s] = true;
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for(auto v : adj[u]) {
            if(vis[v] == false) {
                q.push(v);
                vis[v] = true;
                g[u].push_back(v);
            }
        }
    }
    check = 0;
    dfs(s);
    if(check != n) {
        return;
    }
    int sum = 0;
    for(int i = 1; i <= n; i++) {
        sum += cnt[i];
    }
    res = min(res, sum);
    return;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++) {
        int k; cin >> k;
        while(k--) {
            int v; cin >> v;
            adj[v].push_back(i);
        }
    }
    res = INT_MAX;
    for(int i = 1; i <= n; i++) {
        solve(i);
    }
    cout << res << '\n';
    return 0;
}

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