# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
41141 | 2018-02-13T05:26:23 Z | ssnsarang2023 | Bosses (BOI16_bosses) | C++14 | 695 ms | 1132 KB |
#include <cstdio> #include <vector> using namespace std; typedef long long ll; typedef unsigned long long ull; #define SZ(x) ((int)x.size()) const int N = 5e3+5; int n, sz[N], par[N]; bool vis[N]; vector<int> g[N]; int lo, hi, q[N]; int make_tree(int root) { for (int i = 1; i <= n; ++i) vis[i] = sz[i] = 0; q[1] = root; vis[root] = lo = hi = 1; int cnt = 1; while (lo <= hi) { int u = q[lo++]; for (int i = 0; i < SZ(g[u]); ++i) { int v = g[u][i]; if (vis[v]) continue; ++cnt, vis[v] = true; q[++hi] = v; par[v] = u; } } if (cnt < n) return (int)1e9+7; int sum = 0; sz[0] = 0; for (int i = hi; i >= 1; --i) { ++sz[q[i]]; sz[par[q[i]]] += sz[q[i]]; sum += sz[q[i]]; } return sum; } int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) { int m; scanf("%d", &m); for (int j = 1, v; j <= m; ++j) { scanf("%d", &v); g[v].push_back(i); } } int res = (int)1e9+7; for (int i = 1; i <= n; ++i) res = min(res, make_tree(i)); printf("%d", res); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 480 KB | Output is correct |
3 | Correct | 2 ms | 680 KB | Output is correct |
4 | Correct | 2 ms | 680 KB | Output is correct |
5 | Correct | 1 ms | 680 KB | Output is correct |
6 | Correct | 2 ms | 680 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 480 KB | Output is correct |
3 | Correct | 2 ms | 680 KB | Output is correct |
4 | Correct | 2 ms | 680 KB | Output is correct |
5 | Correct | 1 ms | 680 KB | Output is correct |
6 | Correct | 2 ms | 680 KB | Output is correct |
7 | Correct | 2 ms | 708 KB | Output is correct |
8 | Correct | 1 ms | 728 KB | Output is correct |
9 | Correct | 2 ms | 728 KB | Output is correct |
10 | Correct | 2 ms | 728 KB | Output is correct |
11 | Correct | 2 ms | 728 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 480 KB | Output is correct |
3 | Correct | 2 ms | 680 KB | Output is correct |
4 | Correct | 2 ms | 680 KB | Output is correct |
5 | Correct | 1 ms | 680 KB | Output is correct |
6 | Correct | 2 ms | 680 KB | Output is correct |
7 | Correct | 2 ms | 708 KB | Output is correct |
8 | Correct | 1 ms | 728 KB | Output is correct |
9 | Correct | 2 ms | 728 KB | Output is correct |
10 | Correct | 2 ms | 728 KB | Output is correct |
11 | Correct | 2 ms | 728 KB | Output is correct |
12 | Correct | 6 ms | 744 KB | Output is correct |
13 | Correct | 6 ms | 744 KB | Output is correct |
14 | Correct | 136 ms | 876 KB | Output is correct |
15 | Correct | 31 ms | 876 KB | Output is correct |
16 | Correct | 582 ms | 1004 KB | Output is correct |
17 | Correct | 666 ms | 1004 KB | Output is correct |
18 | Correct | 695 ms | 1132 KB | Output is correct |