# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
338123 | 2020-12-22T14:16:10 Z | MilosMilutinovic | Bosses (BOI16_bosses) | C++14 | 1127 ms | 876 KB |
#include <bits/stdc++.h> using namespace std; #define pb push_back const int N=5050; vector<int> E[N]; int n; int BFS(int u){ bool was[n+1]; int dist[n+1],cnt[n+1],dp[n+1]; for(int i=0;i<=n;i++)was[i]=false,dist[i]=N*2,cnt[i]=0,dp[i]=0; deque<int> q; q.pb(u); dist[u]=0,was[u]=1; while(!q.empty()){ int x=q[0]; for(int c:E[x]){ dist[c]=min(dist[c],dist[x]+1); if(!was[c]){ was[c]=1; q.pb(c); } } q.pop_front(); } for(int i=1;i<=n;i++){ if(dist[i]==2*N)return N*N*2; cnt[dist[i]]++; } for(int i=n-1;i>=0;i--)dp[i]=dp[i+1]+cnt[i]; int ans=0; for(int i=0;i<n;i++)ans+=dp[i]; return ans; } int main(){ scanf("%i",&n); for(int i=1;i<=n;i++){ int sz;scanf("%i",&sz); while(sz--){ int p;scanf("%i",&p); E[p].pb(i); } } int ans=N*N; for(int i=1;i<=n;i++){ int tmp=BFS(i); ans=min(ans,tmp); //printf("%i %i\n",i,tmp); } printf("%i",ans); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 492 KB | Output is correct |
2 | Correct | 1 ms | 492 KB | Output is correct |
3 | Correct | 1 ms | 492 KB | Output is correct |
4 | Correct | 1 ms | 492 KB | Output is correct |
5 | Correct | 1 ms | 492 KB | Output is correct |
6 | Correct | 1 ms | 492 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 492 KB | Output is correct |
2 | Correct | 1 ms | 492 KB | Output is correct |
3 | Correct | 1 ms | 492 KB | Output is correct |
4 | Correct | 1 ms | 492 KB | Output is correct |
5 | Correct | 1 ms | 492 KB | Output is correct |
6 | Correct | 1 ms | 492 KB | Output is correct |
7 | Correct | 1 ms | 492 KB | Output is correct |
8 | Correct | 1 ms | 492 KB | Output is correct |
9 | Correct | 1 ms | 492 KB | Output is correct |
10 | Correct | 1 ms | 492 KB | Output is correct |
11 | Correct | 1 ms | 492 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 492 KB | Output is correct |
2 | Correct | 1 ms | 492 KB | Output is correct |
3 | Correct | 1 ms | 492 KB | Output is correct |
4 | Correct | 1 ms | 492 KB | Output is correct |
5 | Correct | 1 ms | 492 KB | Output is correct |
6 | Correct | 1 ms | 492 KB | Output is correct |
7 | Correct | 1 ms | 492 KB | Output is correct |
8 | Correct | 1 ms | 492 KB | Output is correct |
9 | Correct | 1 ms | 492 KB | Output is correct |
10 | Correct | 1 ms | 492 KB | Output is correct |
11 | Correct | 1 ms | 492 KB | Output is correct |
12 | Correct | 10 ms | 492 KB | Output is correct |
13 | Correct | 8 ms | 492 KB | Output is correct |
14 | Correct | 227 ms | 748 KB | Output is correct |
15 | Correct | 95 ms | 620 KB | Output is correct |
16 | Correct | 741 ms | 748 KB | Output is correct |
17 | Correct | 1099 ms | 748 KB | Output is correct |
18 | Correct | 1127 ms | 876 KB | Output is correct |