# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
531835 | 2022-03-01T15:58:05 Z | kebine | Bosses (BOI16_bosses) | C++17 | 0 ms | 204 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>()); int r = -1; for(int i=0;i<n;i++) { int k; cin >> k; if(k == 0) r = i; for(int j=0;j<k;j++) { int x; cin >> x; x--; adj[x].push_back(i); // incoming edges } } if(r == -1) { int mx = 0; for(int i=0;i<n;i++) { if(adj[i].size() > mx) { mx = adj[i].size(); r = i; } } } assert(r != -1); queue<int> q; q.push(r); vector<int> g[n]; // outcoming edges vector<int> dist(n, -1); dist[r] = 0; while(!q.empty()){ int u = q.front(); q.pop(); for(auto v : adj[u]){ if(dist[v] == -1) { g[u].push_back(v); dist[v] = dist[u] + 1; q.push(v); } } } vector<int> ans(n); vector<bool> vis(n); function<int(int)> Dfs = [&](int v){ int ret = 1; for(auto i : g[v]) { if(!vis[i]){ vis[i] = 1; ret += Dfs(i); } } // cout << v << " : " << ret << '\n'; return ans[v] = ret; }; vis[r] = 1; Dfs(r); int sm = 0; for(int i=0;i<n;i++) { // cout << ans[i] << " "; assert(ans[i] > 0); sm += ans[i]; } cout << sm << '\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 | Correct | 0 ms | 204 KB | Output is correct |
4 | Correct | 0 ms | 204 KB | Output is correct |
5 | Correct | 0 ms | 204 KB | Output is correct |
6 | Correct | 0 ms | 204 KB | Output is correct |
# | 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 | Correct | 0 ms | 204 KB | Output is correct |
4 | Correct | 0 ms | 204 KB | Output is correct |
5 | Correct | 0 ms | 204 KB | Output is correct |
6 | Correct | 0 ms | 204 KB | Output is correct |
7 | Correct | 0 ms | 204 KB | Output is correct |
8 | Incorrect | 0 ms | 204 KB | Output isn't correct |
9 | 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 | Correct | 0 ms | 204 KB | Output is correct |
4 | Correct | 0 ms | 204 KB | Output is correct |
5 | Correct | 0 ms | 204 KB | Output is correct |
6 | Correct | 0 ms | 204 KB | Output is correct |
7 | Correct | 0 ms | 204 KB | Output is correct |
8 | Incorrect | 0 ms | 204 KB | Output isn't correct |
9 | Halted | 0 ms | 0 KB | - |