# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
68909 | 2018-08-19T08:20:06 Z | Vahan | Bosses (BOI16_bosses) | C++17 | 1500 ms | 1968 KB |
#include<iostream> #include<vector> #include<deque> #include<cstdio> using namespace std; vector<int> r[20000],g[20000]; deque<int> q; int n,pp,u[100000],pat=-1; int dfs(int v,int p) { int x=1; for(int i=0;i<r[v].size();i++) { int to=r[v][i]; if(to==p) continue; x+=dfs(to,v); } pp+=x; return x; } int main() { cin>>n; for(int i=1;i<=n;i++) { int a; scanf("%d",&a); for(int j=1;j<=a;j++) { int b; scanf("%d",&b); if(i!=b) g[b].push_back(i); } } for(int i=1;i<=n;i++) { q.push_back(i); u[i]=1; int t=0; while(!q.empty()) { int v=q.front(); q.pop_front(); t++; for(int j=0;j<g[v].size();j++) { int to=g[v][j]; if(u[to]==0) { u[to]=1; q.push_back(to); r[v].push_back(to); } } } if(t==n) { pp=0; dfs(i,-1); if(pp<pat || pat==-1) pat=pp; } else q.clear(); for(int j=1;j<=n;j++) { u[j]=0; r[j].clear(); } } cout<<pat<<endl; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 1272 KB | Output is correct |
2 | Correct | 4 ms | 1360 KB | Output is correct |
3 | Correct | 4 ms | 1360 KB | Output is correct |
4 | Correct | 4 ms | 1444 KB | Output is correct |
5 | Correct | 4 ms | 1532 KB | Output is correct |
6 | Correct | 3 ms | 1532 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 1272 KB | Output is correct |
2 | Correct | 4 ms | 1360 KB | Output is correct |
3 | Correct | 4 ms | 1360 KB | Output is correct |
4 | Correct | 4 ms | 1444 KB | Output is correct |
5 | Correct | 4 ms | 1532 KB | Output is correct |
6 | Correct | 3 ms | 1532 KB | Output is correct |
7 | Correct | 3 ms | 1532 KB | Output is correct |
8 | Correct | 3 ms | 1532 KB | Output is correct |
9 | Correct | 4 ms | 1532 KB | Output is correct |
10 | Correct | 4 ms | 1532 KB | Output is correct |
11 | Correct | 3 ms | 1532 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 1272 KB | Output is correct |
2 | Correct | 4 ms | 1360 KB | Output is correct |
3 | Correct | 4 ms | 1360 KB | Output is correct |
4 | Correct | 4 ms | 1444 KB | Output is correct |
5 | Correct | 4 ms | 1532 KB | Output is correct |
6 | Correct | 3 ms | 1532 KB | Output is correct |
7 | Correct | 3 ms | 1532 KB | Output is correct |
8 | Correct | 3 ms | 1532 KB | Output is correct |
9 | Correct | 4 ms | 1532 KB | Output is correct |
10 | Correct | 4 ms | 1532 KB | Output is correct |
11 | Correct | 3 ms | 1532 KB | Output is correct |
12 | Correct | 10 ms | 1644 KB | Output is correct |
13 | Correct | 8 ms | 1644 KB | Output is correct |
14 | Correct | 240 ms | 1724 KB | Output is correct |
15 | Correct | 51 ms | 1724 KB | Output is correct |
16 | Correct | 848 ms | 1968 KB | Output is correct |
17 | Execution timed out | 1559 ms | 1968 KB | Time limit exceeded |
18 | Halted | 0 ms | 0 KB | - |