# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
531828 | 2022-03-01T15:48:24 Z | devariaota | Bosses (BOI16_bosses) | C++17 | 1 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); } } 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); // cout << "root : " << r << '\n'; 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[u].push_back(v); // child[u]++; dist[v] = dist[u] + 1; q.push(v); } } } vector<int> ans(n); function<int(int)> Dfs = [&](int v){ int ret = 1; for(auto i : g[v]) { ret += Dfs(i); } // cout << v << " : " << ret << '\n'; return ans[v] = ret; }; Dfs(r); int sm = 0; for(int i=0;i<n;i++) { // cout << ans[i] << " "; 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 | 1 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 | 1 ms | 204 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 1 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 | 1 ms | 204 KB | Output is correct |
7 | Correct | 1 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 | 1 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 | 1 ms | 204 KB | Output is correct |
7 | Correct | 1 ms | 204 KB | Output is correct |
8 | Incorrect | 0 ms | 204 KB | Output isn't correct |
9 | Halted | 0 ms | 0 KB | - |