# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
813288 | 2023-08-07T15:03:48 Z | trucmai | Bosses (BOI16_bosses) | C++17 | 476 ms | 24068 KB |
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "/home/trucmai/.vim/tools.h" #define debug(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl; #else #define debug(x...) #endif void open(){ if(fopen("i.inp","r")){ freopen("i.inp","r",stdin); freopen("o.out","w",stdout); } } #define ll long long #define all(a) (a).begin(), (a).end() #define vi vector<ll> #define pi pair<ll,ll> #define pii pair<ll,pair<ll,ll>> #define fi first #define se second #define gcd __gcd #define mset(a,v) memset(a, v, sizeof(a)) #define endl '\n' #define spc " " const int MN = 1e6 + 5,LOG = 27; const ll MOD = 1e9 + 7,INF = 1e9; ll n; vector<ll>g[MN]; ll bfs(ll root){ queue<ll>qu; ll res = 0; vector<ll>h(n+1,0); vector<bool>vis(n+1,false); h[root] = 1; qu.push(root); vis[root] = true; while(!qu.empty()){ ll u = qu.front(); qu.pop(); res += h[u]; for(ll &v : g[u]){ if(vis[v]) continue; h[v] = h[u] + 1; vis[v] = true; qu.push(v); } } bool flag = true; for(ll i = 1;i <= n;++i) flag &= vis[i]; return (flag ? res : INF); } void solve(){ cin>>n; for(ll i = 1;i <= n;++i){ ll k; cin>>k; for(ll j = 1;j <= k;++j){ ll x; cin>>x; g[x].push_back(i); } } ll res = INF; for(ll r = 1;r <= n;++r) res = min(res,bfs(r)); cout<<res<<endl; } signed main(){ cin.tie(0) -> sync_with_stdio(0); open(); ll t = 1; //cin>>t; while(t--) solve(); #ifdef LOCAL cerr << endl << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"; #endif }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 23764 KB | Output is correct |
2 | Correct | 11 ms | 23800 KB | Output is correct |
3 | Correct | 13 ms | 23808 KB | Output is correct |
4 | Correct | 13 ms | 23808 KB | Output is correct |
5 | Correct | 11 ms | 23808 KB | Output is correct |
6 | Correct | 12 ms | 23764 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 23764 KB | Output is correct |
2 | Correct | 11 ms | 23800 KB | Output is correct |
3 | Correct | 13 ms | 23808 KB | Output is correct |
4 | Correct | 13 ms | 23808 KB | Output is correct |
5 | Correct | 11 ms | 23808 KB | Output is correct |
6 | Correct | 12 ms | 23764 KB | Output is correct |
7 | Correct | 12 ms | 23776 KB | Output is correct |
8 | Correct | 11 ms | 23804 KB | Output is correct |
9 | Correct | 11 ms | 23688 KB | Output is correct |
10 | Correct | 14 ms | 23764 KB | Output is correct |
11 | Correct | 12 ms | 23804 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 23764 KB | Output is correct |
2 | Correct | 11 ms | 23800 KB | Output is correct |
3 | Correct | 13 ms | 23808 KB | Output is correct |
4 | Correct | 13 ms | 23808 KB | Output is correct |
5 | Correct | 11 ms | 23808 KB | Output is correct |
6 | Correct | 12 ms | 23764 KB | Output is correct |
7 | Correct | 12 ms | 23776 KB | Output is correct |
8 | Correct | 11 ms | 23804 KB | Output is correct |
9 | Correct | 11 ms | 23688 KB | Output is correct |
10 | Correct | 14 ms | 23764 KB | Output is correct |
11 | Correct | 12 ms | 23804 KB | Output is correct |
12 | Correct | 15 ms | 23892 KB | Output is correct |
13 | Correct | 14 ms | 23892 KB | Output is correct |
14 | Correct | 109 ms | 23892 KB | Output is correct |
15 | Correct | 38 ms | 23960 KB | Output is correct |
16 | Correct | 437 ms | 24068 KB | Output is correct |
17 | Correct | 476 ms | 24052 KB | Output is correct |
18 | Correct | 458 ms | 24052 KB | Output is correct |