# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
53621 | 2018-06-30T14:30:06 Z | ruhanhabib39 | Bosses (BOI16_bosses) | C++17 | 826 ms | 1308 KB |
#include <bits/stdc++.h> using namespace std; const int MAXN = 5000; int N; vector<int> par[MAXN + 10]; vector<int> child[MAXN + 10]; int done[MAXN + 10]; int salary[MAXN + 10]; int vec[MAXN + 10], ii = 0; int boss[MAXN + 10]; int work(int root) { ii = 0; queue<int> q; q.push(root); done[root] = root; boss[root] = -1; while(!q.empty()) { int u = q.front(); q.pop(); vec[ii++] = u; for(int v : child[u]) { if(done[v] == root) continue; done[v] = root; boss[v] = u; q.push(v); } } for(int u = 1; u <= N; u++) { if(done[u] != root) return 1e9; } fill(salary, salary + N + 1, 1); int res = 0; for(int i = ii-1; i >= 0; i--) { int v = vec[i]; if(boss[v] != -1) salary[boss[v]] += salary[v]; res += salary[v]; } return res; } int main() { scanf("%d", &N); for(int u = 1; u <= N; u++) { int sz; scanf("%d", &sz); par[u].resize(sz); for(int& p : par[u]) { scanf("%d", &p); child[p].push_back(u); } } int res = 1e9; for(int u = 1; u <= N; u++) res = min(res, work(u)); printf("%d\n", res); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 632 KB | Output is correct |
2 | Correct | 2 ms | 744 KB | Output is correct |
3 | Correct | 2 ms | 744 KB | Output is correct |
4 | Correct | 2 ms | 744 KB | Output is correct |
5 | Correct | 2 ms | 752 KB | Output is correct |
6 | Correct | 3 ms | 776 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 632 KB | Output is correct |
2 | Correct | 2 ms | 744 KB | Output is correct |
3 | Correct | 2 ms | 744 KB | Output is correct |
4 | Correct | 2 ms | 744 KB | Output is correct |
5 | Correct | 2 ms | 752 KB | Output is correct |
6 | Correct | 3 ms | 776 KB | Output is correct |
7 | Correct | 3 ms | 776 KB | Output is correct |
8 | Correct | 2 ms | 832 KB | Output is correct |
9 | Correct | 2 ms | 876 KB | Output is correct |
10 | Correct | 2 ms | 876 KB | Output is correct |
11 | Correct | 3 ms | 876 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 632 KB | Output is correct |
2 | Correct | 2 ms | 744 KB | Output is correct |
3 | Correct | 2 ms | 744 KB | Output is correct |
4 | Correct | 2 ms | 744 KB | Output is correct |
5 | Correct | 2 ms | 752 KB | Output is correct |
6 | Correct | 3 ms | 776 KB | Output is correct |
7 | Correct | 3 ms | 776 KB | Output is correct |
8 | Correct | 2 ms | 832 KB | Output is correct |
9 | Correct | 2 ms | 876 KB | Output is correct |
10 | Correct | 2 ms | 876 KB | Output is correct |
11 | Correct | 3 ms | 876 KB | Output is correct |
12 | Correct | 9 ms | 892 KB | Output is correct |
13 | Correct | 6 ms | 892 KB | Output is correct |
14 | Correct | 151 ms | 1168 KB | Output is correct |
15 | Correct | 5 ms | 1168 KB | Output is correct |
16 | Correct | 671 ms | 1276 KB | Output is correct |
17 | Correct | 743 ms | 1276 KB | Output is correct |
18 | Correct | 826 ms | 1308 KB | Output is correct |