# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
24762 | 2017-06-13T08:48:31 Z | nibnalin | Bosses (BOI16_bosses) | C++14 | 0 ms | 2316 KB |
#include <iostream> #include <cstdio> #include <vector> #include <set> using namespace std; const int maxn = int(5e3)+5, inf = int(1e9)+5; int n, D[maxn], P[maxn], val[maxn]; vector<int> graph[maxn], tree[maxn]; void dfs(int node) { val[node] = 1; for(auto it: tree[node]) { dfs(it); val[node] += val[it]; } } int solve(int node) { set<pair<int, int>> Q; for(int i = 0;i < n;i++) D[i] = inf; D[node] = 0; Q.insert({0, node}); P[node] = -1; while(!Q.empty()) { pair<int, int> top = *Q.begin(); Q.erase(Q.begin()); for(auto it: graph[top.second]) { if(D[it] > 1+D[top.second]) { if(D[it] != inf) Q.erase({D[it], it}); D[it] = 1+D[top.second]; P[it] = top.second; Q.insert({D[it], it}); } } } for(int i = 0;i < n;i++) tree[i].clear(); for(int i = 0;i < n;i++) { if(P[i] != -1) tree[P[i]].push_back(i); } dfs(node); int ret = 0; for(int i = 0;i < n;i++) ret += val[i]; //cout << "\n" << node << " " << " " << ret << "\n"; return ret; } int main(void) { int p, x; scanf("%d", &n); for(int i = 0;i < n;i++) { scanf("%d", &x); for(int j = 0;j < x;j++) { scanf("%d", &p); p--; graph[p].push_back(i); } } int res = inf; for(int i = 0;i < n;i++) res = min(res, solve(i)); printf("%d\n", res); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2316 KB | Output is correct |
2 | Correct | 0 ms | 2316 KB | Output is correct |
3 | Correct | 0 ms | 2316 KB | Output is correct |
4 | Incorrect | 0 ms | 2316 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2316 KB | Output is correct |
2 | Correct | 0 ms | 2316 KB | Output is correct |
3 | Correct | 0 ms | 2316 KB | Output is correct |
4 | Incorrect | 0 ms | 2316 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2316 KB | Output is correct |
2 | Correct | 0 ms | 2316 KB | Output is correct |
3 | Correct | 0 ms | 2316 KB | Output is correct |
4 | Incorrect | 0 ms | 2316 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |