# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
33840 | 2017-11-03T02:34:36 Z | sinhriv | Bosses (BOI16_bosses) | C++14 | 1253 ms | 2468 KB |
#include <bits/stdc++.h> using namespace std; const int N = 5050; int n; int f[N]; int lst[N]; long long salary[N]; vector < int > gra[N]; vector < pair < int, int > > adj[N]; int main(){ if(fopen("1.inp", "r")){ freopen("1.inp", "r", stdin); } scanf("%d", &n); for(int i = 1; i <= n; ++i){ int m; scanf("%d", &m); for(int j = 1; j <= m; ++j){ int x; scanf("%d", &x); adj[x].emplace_back(i, 0); } } long long ans = 1e18; for(int root = 1; root <= n; ++root){ memset(f, 0, sizeof f); memset(salary, 0, sizeof salary); for(int i = 1; i <= n; ++i){ for(auto &p : adj[i]){ p.second = 0; } } queue < int > bfs; bfs.push(root); f[root] = 1; int sz = 0; while(!bfs.empty()){ int x = bfs.front(); bfs.pop(); lst[++sz] = x; for(auto &p : adj[x]){ if(f[p.first] == 0){ f[p.first] = 1; p.second = 1; bfs.push(p.first); } } } if(sz != n) continue; long long ret = 0; for(int i = sz; i >= 1; --i){ int tot = 0; for(auto p : adj[lst[i]]){ if(p.second) tot += salary[p.first]; } salary[lst[i]] = tot + 1; ret += salary[lst[i]]; } ans = min(ans, ret); } cout << ans; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2336 KB | Output is correct |
2 | Correct | 0 ms | 2336 KB | Output is correct |
3 | Correct | 0 ms | 2336 KB | Output is correct |
4 | Correct | 0 ms | 2336 KB | Output is correct |
5 | Correct | 0 ms | 2336 KB | Output is correct |
6 | Correct | 0 ms | 2336 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2336 KB | Output is correct |
2 | Correct | 0 ms | 2336 KB | Output is correct |
3 | Correct | 0 ms | 2336 KB | Output is correct |
4 | Correct | 0 ms | 2336 KB | Output is correct |
5 | Correct | 0 ms | 2336 KB | Output is correct |
6 | Correct | 0 ms | 2336 KB | Output is correct |
7 | Correct | 0 ms | 2336 KB | Output is correct |
8 | Correct | 0 ms | 2336 KB | Output is correct |
9 | Correct | 0 ms | 2336 KB | Output is correct |
10 | Correct | 0 ms | 2336 KB | Output is correct |
11 | Correct | 0 ms | 2336 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2336 KB | Output is correct |
2 | Correct | 0 ms | 2336 KB | Output is correct |
3 | Correct | 0 ms | 2336 KB | Output is correct |
4 | Correct | 0 ms | 2336 KB | Output is correct |
5 | Correct | 0 ms | 2336 KB | Output is correct |
6 | Correct | 0 ms | 2336 KB | Output is correct |
7 | Correct | 0 ms | 2336 KB | Output is correct |
8 | Correct | 0 ms | 2336 KB | Output is correct |
9 | Correct | 0 ms | 2336 KB | Output is correct |
10 | Correct | 0 ms | 2336 KB | Output is correct |
11 | Correct | 0 ms | 2336 KB | Output is correct |
12 | Correct | 9 ms | 2468 KB | Output is correct |
13 | Correct | 6 ms | 2468 KB | Output is correct |
14 | Correct | 356 ms | 2468 KB | Output is correct |
15 | Correct | 193 ms | 2468 KB | Output is correct |
16 | Correct | 943 ms | 2468 KB | Output is correct |
17 | Correct | 1209 ms | 2468 KB | Output is correct |
18 | Correct | 1253 ms | 2468 KB | Output is correct |