# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
36400 | 2017-12-08T16:21:48 Z | DoanPhuDuc | Bosses (BOI16_bosses) | C++ | 1500 ms | 2684 KB |
#include <bits/stdc++.h> #define FOR(x, a, b) for (int x = a; x <= b; ++x) #define FOD(x, a, b) for (int x = a; x >= b; --x) #define REP(x, a, b) for (int x = a; x < b; ++x) #define DEBUG(X) { cout << #X << " = " << X << endl; } #define PR(A, n) { cout << #A << " = "; FOR(_, 1, n) cout << A[_] << " "; cout << endl; } #define PR0(A, n) { cout << #A << " = "; REP(_, 0, n) cout << A[_] << " "; cout << endl; } using namespace std; typedef long long LL; typedef pair <int, int> II; const int N = 5e3 + 10; const int INF = 0x3f3f3f3f; int n; int f[N]; bool ban[N]; vector <int> boss[N], adj[N]; void DFS(int u) { f[u] = 1; REP(k, 0, adj[u].size()) { int v = adj[u][k]; DFS(v); f[u] += f[v]; } } int Compute(int u) { FOR(i, 1, n) { ban[i] = false; adj[i].clear(); } queue <int> Q1, Q2; Q1.push(u); Q2.push(u); ban[u] = true; while (Q1.size()) { while (Q2.size()) { int u = Q2.front(); Q2.pop(); Q1.pop(); REP(k, 0, boss[u].size()) { int v = boss[u][k]; if (ban[v] == false) { ban[v] = true; Q1.push(v); adj[u].push_back(v); } } } Q2 = Q1; } int num = 0; FOR(i, 1, n) num += ban[i]; if (num == n) { DFS(u); int ans = 0; FOR(i, 1, n) ans += f[i]; return ans; } else return INF; } int main() { #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif // LOCAL scanf("%d", &n); FOR(i, 1, n) { int m; scanf("%d", &m); FOR(j, 1, m) { int x; scanf("%d", &x); boss[x].push_back(i); } } int ans = INF; FOR(i, 1, n) ans = min(ans, Compute(i)); printf("%d\n", ans); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2288 KB | Output is correct |
2 | Correct | 0 ms | 2288 KB | Output is correct |
3 | Correct | 0 ms | 2288 KB | Output is correct |
4 | Correct | 0 ms | 2288 KB | Output is correct |
5 | Correct | 0 ms | 2288 KB | Output is correct |
6 | Correct | 0 ms | 2288 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2288 KB | Output is correct |
2 | Correct | 0 ms | 2288 KB | Output is correct |
3 | Correct | 0 ms | 2288 KB | Output is correct |
4 | Correct | 0 ms | 2288 KB | Output is correct |
5 | Correct | 0 ms | 2288 KB | Output is correct |
6 | Correct | 0 ms | 2288 KB | Output is correct |
7 | Correct | 0 ms | 2288 KB | Output is correct |
8 | Correct | 0 ms | 2288 KB | Output is correct |
9 | Correct | 0 ms | 2288 KB | Output is correct |
10 | Correct | 0 ms | 2288 KB | Output is correct |
11 | Correct | 0 ms | 2288 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2288 KB | Output is correct |
2 | Correct | 0 ms | 2288 KB | Output is correct |
3 | Correct | 0 ms | 2288 KB | Output is correct |
4 | Correct | 0 ms | 2288 KB | Output is correct |
5 | Correct | 0 ms | 2288 KB | Output is correct |
6 | Correct | 0 ms | 2288 KB | Output is correct |
7 | Correct | 0 ms | 2288 KB | Output is correct |
8 | Correct | 0 ms | 2288 KB | Output is correct |
9 | Correct | 0 ms | 2288 KB | Output is correct |
10 | Correct | 0 ms | 2288 KB | Output is correct |
11 | Correct | 0 ms | 2288 KB | Output is correct |
12 | Correct | 6 ms | 2420 KB | Output is correct |
13 | Correct | 3 ms | 2420 KB | Output is correct |
14 | Correct | 579 ms | 2420 KB | Output is correct |
15 | Correct | 66 ms | 2420 KB | Output is correct |
16 | Correct | 1059 ms | 2552 KB | Output is correct |
17 | Execution timed out | 1500 ms | 2684 KB | Execution timed out |
18 | Halted | 0 ms | 0 KB | - |