Submission #306349

#	Time	Username	Problem	Language	Result	Execution time	Memory
306349		kaplanbar	Bosses (BOI16_bosses)	C++14	0 / 100	1 ms	384 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int N = 5e3+5;
int n;
vector<int> adj[N];
int solve(int root) {
    vector<int> val(n, 0), from(n, -1);
    vector<bool> vis(n);
    queue<int> q;
    q.push(root);
    vis[root] = 1;
    stack<int> s;
    while(!q.empty()) {
        int now = q.front();
        q.pop();
        s.push(now);
        for(int v : adj[now]) {
            if(vis[v]) continue;
            from[v] = now;
            vis[v] = 1;
            q.push(v);
        }
    }
    for(int i = 0; i < n; i++) {
        if(!vis[i]) return 1e9;
    }
    while(!s.empty()) {
        int now = s.top();
        s.pop();
        val[now]++;
        if(from[now] != -1) {
            val[from[now]] += val[now];
        }
    }
    int ret = 0;
    for(int i = 0; i < n; i++) ret += val[i];
    return ret;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin >> n;
    for(int i = 0; i < n; i++) {
        int x;
        cin >> x;
        for(int j = 0; j < x; j++) {
            int t;
            cin >> t;
            t--;
            adj[t].push_back(i);
        }
    }
    int ans = 1e9;
    for(int i = 0; i < n; i++) {
        ans = min(ans, solve(i));
    }
    return 0;
}

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