# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
68910 | 2018-08-19T08:29:44 Z | MANcity | Bosses (BOI16_bosses) | C++14 | 996 ms | 1052 KB |
///GAGO_O #include<iostream> #include<cstdio> #include<fstream> #include<algorithm> #include<cmath> #include<map> #include<queue> #include<set> #include<stack> #include<string> #include<cstring> #include<vector> using namespace std; #define for1(i,n) for(int i=1;i<=(int)n;i++) #define for0(i,n) for(int i=0;i<=(int)n;i++) #define forn(i,n) for(int i=n;i>=1;i--) #define fo(i,x,y) for(int i=x;i<=(int)y;i++) #define fr(i,x,y) for(int i=x;i>=(int)y;i--) #define pb push_back #define mp make_pair #define LL long long const LL Mod=1000*1000*1000+7; int n; int used[5002]; vector<vector<int> > g(5002); int d[5002]; int p[5002]; int bfs(int x) { for1(i,n) { used[i]=0; d[i]=0; p[i]=0; } int X=x; queue<int> q; q.push(x); used[x]=1; p[x]=1; while(!q.empty()) { int x=q.front(); for0(j,g[x].size()-1) { int to=g[x][j]; if(used[to]==0) { p[to]=p[x]+1; used[to]=1; q.push(to); } } q.pop(); } for1(i,n) if(used[i]==0) return (100000000); for1(i,n) d[p[i]]++; int u=0; forn(i,n) { if(d[i]!=0) { u=i; break; } } int ANS=0; ANS+=d[u]; forn(i,u-1) ANS+=(d[i]-1); int f[5002]; for1(i,n) f[i]=0; f[u-1]=d[u]+1; forn(i,u-2) { f[i]=(f[i+1]+d[i+1]); } forn(i,u-1) ANS+=f[i]; return ANS; } int main() { scanf("%d",&n); for1(i,n) { int k; scanf("%d",&k); for1(j,k) { int x; scanf("%d",&x); g[x].push_back(i); } } int ans=100000000; for1(i,n) ans=min(ans,bfs(i)); cout<<ans<<endl; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 504 KB | Output is correct |
2 | Correct | 3 ms | 588 KB | Output is correct |
3 | Correct | 3 ms | 640 KB | Output is correct |
4 | Correct | 2 ms | 640 KB | Output is correct |
5 | Correct | 2 ms | 640 KB | Output is correct |
6 | Correct | 3 ms | 640 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 504 KB | Output is correct |
2 | Correct | 3 ms | 588 KB | Output is correct |
3 | Correct | 3 ms | 640 KB | Output is correct |
4 | Correct | 2 ms | 640 KB | Output is correct |
5 | Correct | 2 ms | 640 KB | Output is correct |
6 | Correct | 3 ms | 640 KB | Output is correct |
7 | Correct | 3 ms | 640 KB | Output is correct |
8 | Correct | 2 ms | 640 KB | Output is correct |
9 | Correct | 3 ms | 640 KB | Output is correct |
10 | Correct | 2 ms | 676 KB | Output is correct |
11 | Correct | 3 ms | 676 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 504 KB | Output is correct |
2 | Correct | 3 ms | 588 KB | Output is correct |
3 | Correct | 3 ms | 640 KB | Output is correct |
4 | Correct | 2 ms | 640 KB | Output is correct |
5 | Correct | 2 ms | 640 KB | Output is correct |
6 | Correct | 3 ms | 640 KB | Output is correct |
7 | Correct | 3 ms | 640 KB | Output is correct |
8 | Correct | 2 ms | 640 KB | Output is correct |
9 | Correct | 3 ms | 640 KB | Output is correct |
10 | Correct | 2 ms | 676 KB | Output is correct |
11 | Correct | 3 ms | 676 KB | Output is correct |
12 | Correct | 10 ms | 676 KB | Output is correct |
13 | Correct | 8 ms | 800 KB | Output is correct |
14 | Correct | 236 ms | 1004 KB | Output is correct |
15 | Correct | 71 ms | 1052 KB | Output is correct |
16 | Correct | 821 ms | 1052 KB | Output is correct |
17 | Correct | 996 ms | 1052 KB | Output is correct |
18 | Correct | 985 ms | 1052 KB | Output is correct |