# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
156295 | 2019-10-04T23:57:35 Z | Lawliet | Bosses (BOI16_bosses) | C++14 | 1035 ms | 840 KB |
#include <bits/stdc++.h> #define MAX 5010 #define INF 1000000010 using namespace std; int n; int n1, n2; int ans[MAX]; int dist[MAX]; bool marc[MAX]; vector<int> grafo[MAX]; queue<int> q; void add(int cur, int root, int d) { q.push( cur ); dist[ cur ] = d; marc[ cur ] = true; ans[ root ] += dist[ cur ]; } void BFS(int s) { memset(marc , 0 , sizeof( marc )); add( s , s , 1 ); while( !q.empty() ) { int cur = q.front(); q.pop(); for(int i = 0 ; i < grafo[ cur ].size() ; i++) { int prox = grafo[ cur ][ i ]; if( !marc[prox] ) add( prox , s , dist[ cur ] + 1 ); } } } int main() { scanf("%d",&n); for(int i = 1 ; i <= n ; i++) { scanf("%d",&n1); for(int j = 1 ; j <= n1 ; j++) { scanf("%d",&n2); grafo[ n2 ].push_back( i ); } } int mn = INF; for(int i = 1 ; i <= n ; i++) { BFS( i ); bool reachAll = true; for(int j = 1 ; j <= n ; j++) reachAll = reachAll && marc[ j ]; if( reachAll ) mn = min(mn , ans[ i ]); } printf("%d\n",mn); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 504 KB | Output is correct |
2 | Correct | 2 ms | 504 KB | Output is correct |
3 | Correct | 2 ms | 376 KB | Output is correct |
4 | Correct | 2 ms | 580 KB | Output is correct |
5 | Correct | 2 ms | 504 KB | Output is correct |
6 | Correct | 2 ms | 424 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 504 KB | Output is correct |
2 | Correct | 2 ms | 504 KB | Output is correct |
3 | Correct | 2 ms | 376 KB | Output is correct |
4 | Correct | 2 ms | 580 KB | Output is correct |
5 | Correct | 2 ms | 504 KB | Output is correct |
6 | Correct | 2 ms | 424 KB | Output is correct |
7 | Correct | 2 ms | 376 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 2 ms | 504 KB | Output is correct |
10 | Correct | 2 ms | 376 KB | Output is correct |
11 | Correct | 2 ms | 376 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 504 KB | Output is correct |
2 | Correct | 2 ms | 504 KB | Output is correct |
3 | Correct | 2 ms | 376 KB | Output is correct |
4 | Correct | 2 ms | 580 KB | Output is correct |
5 | Correct | 2 ms | 504 KB | Output is correct |
6 | Correct | 2 ms | 424 KB | Output is correct |
7 | Correct | 2 ms | 376 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 2 ms | 504 KB | Output is correct |
10 | Correct | 2 ms | 376 KB | Output is correct |
11 | Correct | 2 ms | 376 KB | Output is correct |
12 | Correct | 7 ms | 504 KB | Output is correct |
13 | Correct | 6 ms | 504 KB | Output is correct |
14 | Correct | 193 ms | 632 KB | Output is correct |
15 | Correct | 5 ms | 632 KB | Output is correct |
16 | Correct | 744 ms | 840 KB | Output is correct |
17 | Correct | 1035 ms | 732 KB | Output is correct |
18 | Correct | 1004 ms | 764 KB | Output is correct |