oj.uz

답안 #397179

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
397179 2021-05-01T16:47:45 Z keta_tsimakuridze Bosses (BOI16_bosses) C++14
100 / 100
 840 ms 672 KB 
#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N=5005,mod=1e9+7,Inf=1e16;
int t,n,fix[N],h[N];
long long sum;
queue<int> q;
vector<int>V[N];
string s;
 main(){
	// t=1;
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin >> n;
	for(int i=1;i<=n;i++){
		int c,a;
		cin >> c;
		while(c--){
			cin>>a;
			V[a].push_back(i);
		}
	}
	long long ans = Inf;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			fix[j] = 0;
		}
		q.push(i);
		fix[i]=1;  h[i] = 1;
		int cnt = 0;
		sum = 0;
		while(q.size()) { 
			int u=q.front();  
			q.pop();
			cnt++; 
			sum+=h[u];
			for(int j=0;j<V[u].size();j++){
				if(!fix[V[u][j]]) { 
					fix[V[u][j]] = 1; 
					h[V[u][j]] = h[u] + 1;
					q.push(V[u][j]);
				}
			}
		} 
		
		if(cnt==n)ans=min(ans,sum);
	}
	cout<<ans;
}

Compilation message

bosses.cpp:5:32: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+16' to '2147483647' [-Woverflow]
    5 | const int N=5005,mod=1e9+7,Inf=1e16;
      |                                ^~~~
bosses.cpp:11:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   11 |  main(){
      |       ^
bosses.cpp: In function 'int main()':
bosses.cpp:37:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |    for(int j=0;j<V[u].size();j++){
      |                ~^~~~~~~~~~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 6 ms 460 KB Output is correct
13 Correct 4 ms 460 KB Output is correct
14 Correct 187 ms 564 KB Output is correct
15 Correct 15 ms 588 KB Output is correct
16 Correct 719 ms 656 KB Output is correct
17 Correct 840 ms 668 KB Output is correct
18 Correct 836 ms 672 KB Output is correct