# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
30680 | 2017-07-26T06:00:57 Z | zoomswk | Bosses (BOI16_bosses) | C++14 | 1036 ms | 2244 KB |
#include <stdio.h> #include <vector> #include <queue> using namespace std; vector<int> way[5005]; int par[5005], deg[5005]; int val[5005]; int main(){ int n; scanf("%d", &n); for(int i=1; i<=n; i++){ int k; scanf("%d", &k); while(k--){ int x; scanf("%d", &x); way[x].push_back(i); } } int res = 1e9; for(int root=1; root<=n; root++){ queue<int> q; q.push(root); for(int i=1; i<=n; i++) par[i] = 0, deg[i] = 0, val[i] = 1; par[root] = root; while(!q.empty()){ int pos = q.front(); q.pop(); for(int v : way[pos]) if(!par[v]){ q.push(v); par[v] = pos; deg[pos]++; } } int valid = 1; for(int i=1; i<=n; i++){ if(!par[i]){ valid = 0; break; } } if(!valid) continue; for(int i=1; i<=n; i++) if(deg[i] == 0) q.push(i); int cur = 0; while(!q.empty()){ int pos = q.front(); q.pop(); cur += val[pos]; val[par[pos]] += val[pos]; deg[par[pos]]--; if(deg[par[pos]] == 0) q.push(par[pos]); } if(cur < res) res = cur; } printf("%d", res); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2112 KB | Output is correct |
2 | Correct | 0 ms | 2112 KB | Output is correct |
3 | Correct | 0 ms | 2112 KB | Output is correct |
4 | Correct | 0 ms | 2112 KB | Output is correct |
5 | Correct | 0 ms | 2112 KB | Output is correct |
6 | Correct | 0 ms | 2112 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2112 KB | Output is correct |
2 | Correct | 0 ms | 2112 KB | Output is correct |
3 | Correct | 0 ms | 2112 KB | Output is correct |
4 | Correct | 0 ms | 2112 KB | Output is correct |
5 | Correct | 0 ms | 2112 KB | Output is correct |
6 | Correct | 0 ms | 2112 KB | Output is correct |
7 | Correct | 0 ms | 2112 KB | Output is correct |
8 | Correct | 0 ms | 2112 KB | Output is correct |
9 | Correct | 0 ms | 2112 KB | Output is correct |
10 | Correct | 0 ms | 2112 KB | Output is correct |
11 | Correct | 0 ms | 2112 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2112 KB | Output is correct |
2 | Correct | 0 ms | 2112 KB | Output is correct |
3 | Correct | 0 ms | 2112 KB | Output is correct |
4 | Correct | 0 ms | 2112 KB | Output is correct |
5 | Correct | 0 ms | 2112 KB | Output is correct |
6 | Correct | 0 ms | 2112 KB | Output is correct |
7 | Correct | 0 ms | 2112 KB | Output is correct |
8 | Correct | 0 ms | 2112 KB | Output is correct |
9 | Correct | 0 ms | 2112 KB | Output is correct |
10 | Correct | 0 ms | 2112 KB | Output is correct |
11 | Correct | 0 ms | 2112 KB | Output is correct |
12 | Correct | 3 ms | 2244 KB | Output is correct |
13 | Correct | 3 ms | 2244 KB | Output is correct |
14 | Correct | 166 ms | 2244 KB | Output is correct |
15 | Correct | 49 ms | 2244 KB | Output is correct |
16 | Correct | 653 ms | 2244 KB | Output is correct |
17 | Correct | 993 ms | 2244 KB | Output is correct |
18 | Correct | 1036 ms | 2244 KB | Output is correct |