# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
208532 | 2020-03-11T13:15:38 Z | jzh | Bosses (BOI16_bosses) | C++14 | 1500 ms | 860 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; vector<ll>v[5010]; ll level[5010]; bool vis[5010]; ll sum; ll dfs(ll node){ //if (vis[node])return 0; vis[node]=1; ll ret=0; for (ll i=0;i<v[node].size();i++){ if (level[v[node][i]]==level[node]+1&&!vis[v[node][i]]){ ret+=dfs(v[node][i]); } } ret++; sum+=ret; //cout<<node<<' '<<ret<<'\n'; return ret; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); ll n,i,x,y,k,ans=INT_MAX,i1,w,cnt; cin>>n; for (i=1;i<=n;i++){ cin>>k; while (k--){ cin>>x; v[x].push_back(i); } } for (i=1;i<=n;i++){ queue<pair<ll,ll> >q; q.push({1,i}); for (i1=1;i1<=n;i1++)level[i1]=-1,vis[i1]=0; level[i]=1; sum=0; cnt=0; while (!q.empty()){ x=q.front().second; w=q.front().first; q.pop(); cnt++; for (i1=0;i1<v[x].size();i1++){ if (level[v[x][i1]]==-1){ level[v[x][i1]]=w+1; q.push({w+1,v[x][i1]}); //cout<<x<<'.'<<v[x][i1]<<'\n'; } } } if (cnt<n){ continue; } dfs(i); ans=min(ans,sum); //cout<<i<<'\n'; //cout<<sum<<'\n'; } cout<<ans<<'\n'; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 504 KB | Output is correct |
2 | Correct | 5 ms | 504 KB | Output is correct |
3 | Correct | 5 ms | 504 KB | Output is correct |
4 | Correct | 5 ms | 504 KB | Output is correct |
5 | Correct | 5 ms | 504 KB | Output is correct |
6 | Correct | 5 ms | 504 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 504 KB | Output is correct |
2 | Correct | 5 ms | 504 KB | Output is correct |
3 | Correct | 5 ms | 504 KB | Output is correct |
4 | Correct | 5 ms | 504 KB | Output is correct |
5 | Correct | 5 ms | 504 KB | Output is correct |
6 | Correct | 5 ms | 504 KB | Output is correct |
7 | Correct | 5 ms | 504 KB | Output is correct |
8 | Correct | 5 ms | 504 KB | Output is correct |
9 | Correct | 5 ms | 504 KB | Output is correct |
10 | Correct | 5 ms | 504 KB | Output is correct |
11 | Correct | 5 ms | 504 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 504 KB | Output is correct |
2 | Correct | 5 ms | 504 KB | Output is correct |
3 | Correct | 5 ms | 504 KB | Output is correct |
4 | Correct | 5 ms | 504 KB | Output is correct |
5 | Correct | 5 ms | 504 KB | Output is correct |
6 | Correct | 5 ms | 504 KB | Output is correct |
7 | Correct | 5 ms | 504 KB | Output is correct |
8 | Correct | 5 ms | 504 KB | Output is correct |
9 | Correct | 5 ms | 504 KB | Output is correct |
10 | Correct | 5 ms | 504 KB | Output is correct |
11 | Correct | 5 ms | 504 KB | Output is correct |
12 | Correct | 16 ms | 504 KB | Output is correct |
13 | Correct | 15 ms | 632 KB | Output is correct |
14 | Correct | 255 ms | 632 KB | Output is correct |
15 | Correct | 49 ms | 632 KB | Output is correct |
16 | Correct | 847 ms | 860 KB | Output is correct |
17 | Execution timed out | 1589 ms | 632 KB | Time limit exceeded |
18 | Halted | 0 ms | 0 KB | - |