# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
531804 | 2022-03-01T14:44:57 Z | devariaota | Bosses (BOI16_bosses) | C++17 | 1 ms | 312 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; 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]; // real tree vector<int> dist(n, -1), child(n); dist[r] = 0; // cout << "root : " << r << '\n'; 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); vector<bool> vis(n); 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(); // cout << x + 1 << " -> " ; for(auto i : g[x]) { // cout << x + 1 << " -> " << i + 1 << '\n'; q2.push(i); d[i] += d[x]; vis[i] = 1; } } 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 | 1 ms | 256 KB | Output is correct |
2 | Correct | 1 ms | 312 KB | Output is correct |
3 | Incorrect | 1 ms | 204 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 256 KB | Output is correct |
2 | Correct | 1 ms | 312 KB | Output is correct |
3 | Incorrect | 1 ms | 204 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 256 KB | Output is correct |
2 | Correct | 1 ms | 312 KB | Output is correct |
3 | Incorrect | 1 ms | 204 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |