oj.uz

Submission #936316

# Submission time Handle Problem Language Result Execution time Memory
936316 2024-03-01T15:02:28 Z wateronenn Bosses (BOI16_bosses) C++14
100 / 100
 396 ms 3156 KB 
#include<bits/stdc++.h>
#define pii pair<int,int>
#define f first
#define s second
#define ll long long
using namespace std;

const int N = 1e5+9;
vector<int> g[N];

int main(){
	cin.tie(0)->sync_with_stdio(false);
	int n,m;
	cin>>n;
	for(int i=1;i<=n;i++){
		int k;
		cin>>k;
		for(int j=1;j<=k;j++){
			cin>>m;
			g[m].push_back(i);
		}
	}
	ll sum = LLONG_MAX;
	
	for(int i=1;i<=n;i++){
		bool visit[n+1]={0};
		memset(visit,0,sizeof(visit));
		visit[i] = true;
		queue<pii> s;
		s.push({i,1});
		ll nub = 1;
		int cnt = 1; //count node
		while(!s.empty()){
			int u = s.front().f;
			int w = s.front().s;
		//	cout<<u<<","<<w<<"* ";
			s.pop();
			for(auto v:g[u]){
				if(visit[v]) continue;
				visit[v] = true;
				cnt++;
				nub+=(w+1);
				s.push({v,w+1});
			}
		}
	//	cout<<nub<<" "<<cnt<<endl;
		if(cnt<n) continue;
		sum = min(sum,nub);
	
	}
	cout<<sum;
	
	return 0;
}
/*

4
1 4
3 1 3 4
2 1 2
1 3

4
1 2
0
1 4
0 

*/

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2732 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2732 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 2 ms 2808 KB Output is correct
9 Correct 1 ms 2648 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 1 ms 2648 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2732 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 2 ms 2808 KB Output is correct
9 Correct 1 ms 2648 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 1 ms 2648 KB Output is correct
12 Correct 4 ms 2908 KB Output is correct
13 Correct 3 ms 2908 KB Output is correct
14 Correct 95 ms 2908 KB Output is correct
15 Correct 3 ms 2908 KB Output is correct
16 Correct 396 ms 3152 KB Output is correct
17 Correct 376 ms 2904 KB Output is correct
18 Correct 387 ms 3156 KB Output is correct