# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
30683 | 2017-07-26T06:06:09 Z | noobprogrammer | Bosses (BOI16_bosses) | C++14 | 666 ms | 2352 KB |
#include <bits/stdc++.h> using namespace std ; typedef long long ll ; #define ii pair<int,int> #define fi first #define se second #define vi vector<int> #define vii vector<ii> int n , m , visited[5005] , h[5005] ; ll dp[5005] , res = 1e18 ; queue<int> q ; vi adj[5005] ; void bfs(int x){ memset(visited , 0 , sizeof visited) ; q.push(x); h[x] = 1 ; ll sum = 0 ; visited[x] = 1 ; int cur ,cnt = 0 ; while(!q.empty()){ cur = q.front() ; q.pop() ; cnt++ ; sum += (ll)h[cur] ; for(int v : adj[cur]){ if(visited[v]) continue ; visited[v] = 1 ; h[v] = h[cur] + 1 ; q.push(v) ; } } if(cnt == n) res = min(res , sum ); // printf("%d : %lld %lld\n" ,x , sum , res ); // for(int i = 1 ; i<=n;i++) printf("%d " , h[i]) ; // cout <<endl ; } int main(){ // freopen("in.txt" , "r" , stdin) ; scanf("%d" ,&n) ; int a ,b ; for(int i=1;i<=n;i++){ scanf("%d" , &a); for(int j=0;j<a;j++){ scanf("%d" , &b) ; adj[b].push_back(i) ; } } for(int i=1;i<=n;i++) bfs(i) ; printf("%lld\n" , res) ; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2220 KB | Output is correct |
2 | Correct | 0 ms | 2220 KB | Output is correct |
3 | Correct | 0 ms | 2220 KB | Output is correct |
4 | Correct | 0 ms | 2220 KB | Output is correct |
5 | Correct | 0 ms | 2220 KB | Output is correct |
6 | Correct | 0 ms | 2220 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2220 KB | Output is correct |
2 | Correct | 0 ms | 2220 KB | Output is correct |
3 | Correct | 0 ms | 2220 KB | Output is correct |
4 | Correct | 0 ms | 2220 KB | Output is correct |
5 | Correct | 0 ms | 2220 KB | Output is correct |
6 | Correct | 0 ms | 2220 KB | Output is correct |
7 | Correct | 0 ms | 2220 KB | Output is correct |
8 | Correct | 0 ms | 2220 KB | Output is correct |
9 | Correct | 0 ms | 2220 KB | Output is correct |
10 | Correct | 0 ms | 2220 KB | Output is correct |
11 | Correct | 0 ms | 2220 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2220 KB | Output is correct |
2 | Correct | 0 ms | 2220 KB | Output is correct |
3 | Correct | 0 ms | 2220 KB | Output is correct |
4 | Correct | 0 ms | 2220 KB | Output is correct |
5 | Correct | 0 ms | 2220 KB | Output is correct |
6 | Correct | 0 ms | 2220 KB | Output is correct |
7 | Correct | 0 ms | 2220 KB | Output is correct |
8 | Correct | 0 ms | 2220 KB | Output is correct |
9 | Correct | 0 ms | 2220 KB | Output is correct |
10 | Correct | 0 ms | 2220 KB | Output is correct |
11 | Correct | 0 ms | 2220 KB | Output is correct |
12 | Correct | 3 ms | 2352 KB | Output is correct |
13 | Correct | 3 ms | 2352 KB | Output is correct |
14 | Correct | 119 ms | 2352 KB | Output is correct |
15 | Correct | 3 ms | 2352 KB | Output is correct |
16 | Correct | 666 ms | 2352 KB | Output is correct |
17 | Correct | 639 ms | 2352 KB | Output is correct |
18 | Correct | 639 ms | 2352 KB | Output is correct |