# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
32714 | 2017-10-14T11:23:35 Z | jjwdi0 | Bosses (BOI16_bosses) | C++11 | 1500 ms | 2672 KB |
#include <bits/stdc++.h> using namespace std; int N, sz[5003]; vector<int> v[5003]; vector<int> tree[5003]; bool visited[5003]; queue<int> q; void dfs(int x, int p) { for(int it : tree[x]) { if(it == p) continue; dfs(it, x); sz[x] += sz[it]; } sz[x]++; } int score(int x) { dfs(x, 0); int res = 0; for(int i=1; i<=N; i++) { if(sz[i]) res += sz[i]; else res = 1e9; } return res; } int main() { scanf("%d", &N); for(int i=1, x; i<=N; i++) { scanf("%d", &x); for(int j=0, y; j<x; j++) { scanf("%d", &y); v[y].push_back(i); } } int ans = 2e9; for(int i=1; i<=N; i++) { q.push(i); for(int j=1; j<=N; j++) visited[j] = 0, sz[j] = 0, tree[j].clear(); visited[i] = 1; while(!q.empty()) { int u = q.front(); q.pop(); for(int it : v[u]) { if(visited[it]) continue; tree[u].push_back(it); tree[it].push_back(u); visited[it] = 1; q.push(it); } } ans = min(ans, score(i)); } printf("%d\n", ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2276 KB | Output is correct |
2 | Correct | 0 ms | 2276 KB | Output is correct |
3 | Correct | 0 ms | 2276 KB | Output is correct |
4 | Correct | 0 ms | 2276 KB | Output is correct |
5 | Correct | 0 ms | 2276 KB | Output is correct |
6 | Correct | 0 ms | 2276 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2276 KB | Output is correct |
2 | Correct | 0 ms | 2276 KB | Output is correct |
3 | Correct | 0 ms | 2276 KB | Output is correct |
4 | Correct | 0 ms | 2276 KB | Output is correct |
5 | Correct | 0 ms | 2276 KB | Output is correct |
6 | Correct | 0 ms | 2276 KB | Output is correct |
7 | Correct | 0 ms | 2276 KB | Output is correct |
8 | Correct | 0 ms | 2276 KB | Output is correct |
9 | Correct | 0 ms | 2276 KB | Output is correct |
10 | Correct | 0 ms | 2276 KB | Output is correct |
11 | Correct | 0 ms | 2276 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2276 KB | Output is correct |
2 | Correct | 0 ms | 2276 KB | Output is correct |
3 | Correct | 0 ms | 2276 KB | Output is correct |
4 | Correct | 0 ms | 2276 KB | Output is correct |
5 | Correct | 0 ms | 2276 KB | Output is correct |
6 | Correct | 0 ms | 2276 KB | Output is correct |
7 | Correct | 0 ms | 2276 KB | Output is correct |
8 | Correct | 0 ms | 2276 KB | Output is correct |
9 | Correct | 0 ms | 2276 KB | Output is correct |
10 | Correct | 0 ms | 2276 KB | Output is correct |
11 | Correct | 0 ms | 2276 KB | Output is correct |
12 | Correct | 0 ms | 2408 KB | Output is correct |
13 | Correct | 3 ms | 2408 KB | Output is correct |
14 | Correct | 573 ms | 2572 KB | Output is correct |
15 | Correct | 93 ms | 2540 KB | Output is correct |
16 | Execution timed out | 1500 ms | 2672 KB | Execution timed out |
17 | Halted | 0 ms | 0 KB | - |