# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
289939 | 2020-09-03T08:49:59 Z | BeanZ | Bosses (BOI16_bosses) | C++14 | 1217 ms | 900 KB |
#include <bits/stdc++.h> using namespace std; #define ll long long #define endl '\n' const int N = 5e5 + 5; ll res; ll vis[5005], cnt[5005]; vector<ll> node[5005]; void bfs(ll u){ memset(vis, 0, sizeof(vis)); memset(cnt, 0, sizeof(cnt)); queue<ll> q; stack<pair<ll, ll>> s; s.push({u, 0}); q.push(u); vis[u] = 1; while (q.size()){ ll x = q.front(); q.pop(); for (auto j : node[x]){ if (vis[j]) continue; vis[j] = 1; q.push(j); s.push({j, x}); } } while (s.size()){ cnt[s.top().first]++; res = res + cnt[s.top().first]; cnt[s.top().second] += cnt[s.top().first]; s.pop(); } } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); if (fopen("simplify.in", "r")){ freopen("simplify.in", "r", stdin); freopen("simplify.out", "w", stdout); } ll n; cin >> n; for (int i = 1; i <= n; i++){ ll k; cin >> k; for (int j = 1; j <= k; j++){ ll u; cin >> u; node[u].push_back(i); } } ll ans = 1e18; for (int i = 1; i <= n; i++){ res = 0; bfs(i); bool flag = true; for (int j = 1; j <= n; j++){ if (vis[j] == 0) flag = false; } if (flag) ans = min(ans, res); } cout << ans; } /* */
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 512 KB | Output is correct |
2 | Correct | 1 ms | 512 KB | Output is correct |
3 | Correct | 1 ms | 512 KB | Output is correct |
4 | Correct | 1 ms | 512 KB | Output is correct |
5 | Correct | 1 ms | 512 KB | Output is correct |
6 | Correct | 1 ms | 512 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 512 KB | Output is correct |
2 | Correct | 1 ms | 512 KB | Output is correct |
3 | Correct | 1 ms | 512 KB | Output is correct |
4 | Correct | 1 ms | 512 KB | Output is correct |
5 | Correct | 1 ms | 512 KB | Output is correct |
6 | Correct | 1 ms | 512 KB | Output is correct |
7 | Correct | 1 ms | 512 KB | Output is correct |
8 | Correct | 1 ms | 512 KB | Output is correct |
9 | Correct | 1 ms | 512 KB | Output is correct |
10 | Correct | 1 ms | 512 KB | Output is correct |
11 | Correct | 1 ms | 512 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 512 KB | Output is correct |
2 | Correct | 1 ms | 512 KB | Output is correct |
3 | Correct | 1 ms | 512 KB | Output is correct |
4 | Correct | 1 ms | 512 KB | Output is correct |
5 | Correct | 1 ms | 512 KB | Output is correct |
6 | Correct | 1 ms | 512 KB | Output is correct |
7 | Correct | 1 ms | 512 KB | Output is correct |
8 | Correct | 1 ms | 512 KB | Output is correct |
9 | Correct | 1 ms | 512 KB | Output is correct |
10 | Correct | 1 ms | 512 KB | Output is correct |
11 | Correct | 1 ms | 512 KB | Output is correct |
12 | Correct | 9 ms | 640 KB | Output is correct |
13 | Correct | 5 ms | 768 KB | Output is correct |
14 | Correct | 315 ms | 800 KB | Output is correct |
15 | Correct | 32 ms | 768 KB | Output is correct |
16 | Correct | 975 ms | 900 KB | Output is correct |
17 | Correct | 1217 ms | 896 KB | Output is correct |
18 | Correct | 1159 ms | 896 KB | Output is correct |