oj.uz

답안 #895453

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
895453 2023-12-30T00:53:37 Z thunopro Bosses (BOI16_bosses) C++14
100 / 100
 488 ms 6228 KB 
#include<bits/stdc++.h>
using namespace std ; 
#define ll long long 
#define maxn 200009 
#define fi first 
#define se second 
#define pb push_back 
#define left id<<1 
#define right id<<1|1 
#define re exit(0); 
#define _lower(v,x) lower_bound(v.begin(),v.end(),x)-v.begin()+1  

const int mod = 1e9+7 ; 
const int INF = 1e9 ; 
const int LOG = 18 ; 

typedef vector<int> vi ; 
typedef pair<int,int> pii ; 
typedef vector<ll> vl ; 
typedef vector<pii> vii ; 
 
void add ( int &a , int b ) 
{
	a += b ;
	if ( a < 0 ) a += mod ; 
	if ( a >= mod ) a -= mod ; 
}

template < typename T > void chkmin ( T &a , T b ) { if ( a > b ) a = b ; } 
template < typename T > void chkmax ( T &a , T b ) { if ( a < b ) a = b ; } 

void rf () 
{
	freopen ("bai1.inp","r",stdin) ; 
//	freopen ("bai1.out","w",stdout) ; 
}

int _pow ( int a , int n ) 
{
	if ( n == 0 ) return 1 ; 
	int res = _pow (a,n/2) ; 
	if ( n % 2 ) return 1ll*res*res%mod*a%mod ; 
	else return 1ll*res*res%mod ; 
}

int n ; 
vi adjList [maxn] ; 
int res = 1e9 ; 
int dep [maxn] ; 
int main () 
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0) ; 
//	rf () ; 
	cin >> n ; 
	for ( int i = 1 ; i <= n ; i ++ ) 
	{
		int num ; cin >> num ; 
		for ( int j = 1 ; j <= num ; j ++ ) 
		{
			int x ; cin >> x ; 
			adjList [x] . pb (i) ; 
		}
	}
	
	for ( int root = 1 ; root <= n ; root ++ ) 
	{
		memset ( dep , 0 , sizeof dep ) ; 
		dep [root] = 1 ; 
		queue <int> q ; 
		q . push (root) ; 
		while ( !q.empty() ) 
		{
			int u = q.front() ; q.pop() ; 
			for ( auto v : adjList [u] ) 
			{
				if ( dep [v] == 0 ) 
				{
					dep [v] = dep [u] + 1 ; 
					q.push(v) ; 
				}
			}
		}
		int sum = 0 ; 
		for ( int i = 1 ; i <= n ; i ++ ) 
		{
			sum += dep [i] ; 
			if ( dep [i] == 0 ) sum = 1e9 ; 
		}
		res = min (res,sum) ; 
	}
	cout << res ; 
}

Compilation message

bosses.cpp: In function 'void rf()':
bosses.cpp:34:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |  freopen ("bai1.inp","r",stdin) ;
      |  ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5724 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 2 ms 5724 KB Output is correct
4 Correct 2 ms 5720 KB Output is correct
5 Correct 2 ms 5724 KB Output is correct
6 Correct 2 ms 5724 KB Output is correct

Subtask #2
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5724 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 2 ms 5724 KB Output is correct
4 Correct 2 ms 5720 KB Output is correct
5 Correct 2 ms 5724 KB Output is correct
6 Correct 2 ms 5724 KB Output is correct
7 Correct 3 ms 5724 KB Output is correct
8 Correct 2 ms 5724 KB Output is correct
9 Correct 2 ms 5724 KB Output is correct
10 Correct 3 ms 5720 KB Output is correct
11 Correct 3 ms 5724 KB Output is correct

Subtask #3
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5724 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 2 ms 5724 KB Output is correct
4 Correct 2 ms 5720 KB Output is correct
5 Correct 2 ms 5724 KB Output is correct
6 Correct 2 ms 5724 KB Output is correct
7 Correct 3 ms 5724 KB Output is correct
8 Correct 2 ms 5724 KB Output is correct
9 Correct 2 ms 5724 KB Output is correct
10 Correct 3 ms 5720 KB Output is correct
11 Correct 3 ms 5724 KB Output is correct
12 Correct 7 ms 6056 KB Output is correct
13 Correct 5 ms 6028 KB Output is correct
14 Correct 157 ms 6024 KB Output is correct
15 Correct 76 ms 5976 KB Output is correct
16 Correct 488 ms 6228 KB Output is correct
17 Correct 463 ms 5976 KB Output is correct
18 Correct 473 ms 6136 KB Output is correct