# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
134576 | 2019-07-23T04:26:32 Z | junodeveloper | Bosses (BOI16_bosses) | C++14 | 989 ms | 760 KB |
#include <bits/stdc++.h> #define sz(x) ((int)x.size()) #define all(x) (x).begin(), (x).end() using namespace std; typedef long long ll; typedef long double ld; int n, D[5010], C[5010]; vector<int> adj[5010]; int main() { int i,j; scanf("%d",&n); for(i=1;i<=n;i++) { int k; scanf("%d",&k); for(j=1;j<=k;j++) { int x; scanf("%d",&x); adj[x].push_back(i); } } queue<int> q; int u,mx,tot,res=2e9; for(i=1;i<=n;i++) { fill(D+1,D+n+1,-1); fill(C,C+n+1,0); mx=D[i]=0; q.push(i); tot=0; while(!q.empty()) { u=q.front();q.pop(); C[D[u]]++; mx=max(mx,D[u]); tot++; for(auto& it:adj[u]){ if(D[it]==-1) { D[it]=D[u]+1; q.push(it); } } } if(tot<n) continue; int v=0; for(j=mx;j>=0;j--) { C[j]+=C[j+1]; v+=C[j]; } res=min(res,v); } printf("%d",res); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 376 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Correct | 2 ms | 504 KB | Output is correct |
6 | Correct | 2 ms | 504 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 376 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Correct | 2 ms | 504 KB | Output is correct |
6 | Correct | 2 ms | 504 KB | Output is correct |
7 | Correct | 2 ms | 504 KB | Output is correct |
8 | Correct | 2 ms | 504 KB | Output is correct |
9 | Correct | 2 ms | 504 KB | Output is correct |
10 | Correct | 2 ms | 504 KB | Output is correct |
11 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 376 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Correct | 2 ms | 504 KB | Output is correct |
6 | Correct | 2 ms | 504 KB | Output is correct |
7 | Correct | 2 ms | 504 KB | Output is correct |
8 | Correct | 2 ms | 504 KB | Output is correct |
9 | Correct | 2 ms | 504 KB | Output is correct |
10 | Correct | 2 ms | 504 KB | Output is correct |
11 | Correct | 2 ms | 376 KB | Output is correct |
12 | Correct | 6 ms | 504 KB | Output is correct |
13 | Correct | 5 ms | 632 KB | Output is correct |
14 | Correct | 181 ms | 632 KB | Output is correct |
15 | Correct | 28 ms | 632 KB | Output is correct |
16 | Correct | 682 ms | 708 KB | Output is correct |
17 | Correct | 989 ms | 760 KB | Output is correct |
18 | Correct | 952 ms | 760 KB | Output is correct |