# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
531811 | 2022-03-01T15:11:16 Z | andecaandeci | Bosses (BOI16_bosses) | C++17 | 1 ms | 460 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define int ll signed main(){ cin.tie(0) -> ios_base::sync_with_stdio(0); int n; cin >> n; vector<vector<int>> adj(n, vector<int>()); for(int i=0;i<n;i++) { int k; cin >> k; assert(k > 0); for(int j=0;j<k;j++) { int x; cin >> x; x--; adj[x].push_back(i); } } int mx = 0, r = 0; for(int i=0;i<n;i++) { if(adj[i].size() > mx) { mx = adj[i].size(); r = i; } } queue<int> q; q.push(r); vector<int> g[n]; // directed tree vector<int> dist(n, -1), child(n); dist[r] = 0; while(!q.empty()){ int u = q.front(); q.pop(); for(auto v : adj[u]){ if(dist[v] == -1) { g[v].push_back(u); child[u]++; dist[v] = dist[u] + 1; q.push(v); } } } vector<int> d(n, 1); queue<int> q2; for(int i=0;i<n;i++) { if(!child[i]) { q2.push(i); } } while(!q2.empty()){ int x = q2.front(); q2.pop(); for(auto i : g[x]) { // cout << x + 1 << " -> " << i + 1 << '\n'; q2.push(i); d[i] += d[x]; } } int ans = 0; for(int i=0;i<n;i++) ans += d[i]; cout << ans << '\n'; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Runtime error | 1 ms | 460 KB | Execution killed with signal 6 |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Runtime error | 1 ms | 460 KB | Execution killed with signal 6 |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Runtime error | 1 ms | 460 KB | Execution killed with signal 6 |
4 | Halted | 0 ms | 0 KB | - |