# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
509328 | 2022-01-14T05:02:15 Z | sumit_kk10 | Bosses (BOI16_bosses) | C++17 | 16 ms | 31580 KB |
#include <bits/stdc++.h> #define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL) #define ll long long #define pb push_back #define F first #define S second using namespace std; const int N = 1e6 + 5, MOD = 1e9 + 7; int n, sum = 0; vector<int> g[N], vis(N), dis(N); void solve(){ cin >> n; for(int i = 1; i <= n; ++i){ int x; cin >> x; for(int j = 0; j < x; ++j){ int k; cin >> k; g[k].pb(i); } } long long ans = INT_MAX; for(int root = 1; root <= n; ++root){ for(int j = 1; j <= n; ++j) vis[j] = 0; queue<pair<int, int> > q; int mx = 1; q.push({root, 1}); dis[root] = 1; vis[root] = true; while(!q.empty()){ int node = q.front().F, cost = q.front().S; q.pop(); for(auto k : g[node]){ if(!vis[k]){ q.push({k, cost + 1}); dis[k] = cost + 1; mx = max(mx, cost + 1); vis[k] = true; } } } long long sum = 0; for(int i = 1; i <= n; ++i) sum += mx - dis[i] + 1; ans = min(ans, sum); // cout << sum << ' '; } cout << ans << '\n'; } int main() { fast; int t = 1; // cin >> t; while(t--) solve(); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 31564 KB | Output is correct |
2 | Incorrect | 16 ms | 31580 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 31564 KB | Output is correct |
2 | Incorrect | 16 ms | 31580 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 31564 KB | Output is correct |
2 | Incorrect | 16 ms | 31580 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |