oj.uz

Submission #484663

# Submission time Handle Problem Language Result Execution time Memory
484663 2021-11-05T02:00:58 Z minhcool Bosses (BOI16_bosses) C++17
0 / 100
 2 ms 2636 KB 
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 1e5 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

int n;

vector<int> Adj[N];

int ans = oo;

int mn_dist[N];

void bfss(int u){
	for(int i = 1; i <= n; i++) mn_dist[i] = oo;
	mn_dist[u] = 0;
	queue<int> bfs;
	bfs.push(u);
	while(!bfs.empty()){
		int u = bfs.front();
		bfs.pop();
		for(auto v : Adj[u]){
			if(mn_dist[v] != oo) continue;
			mn_dist[v] = mn_dist[u] + 1;
			bfs.push(v);
		}
	}
	int tol = 0;
	for(int i = 1; i <= n; i++){
		cout << u << " " << i << " " << mn_dist[i] << "\n";
		if(mn_dist[i] == oo){
			tol += mn_dist[i];
			break;
		}
		tol += mn_dist[i];
	}
	ans = min(ans, tol);
}

void process(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		int x;
		cin >> x;
		while(x--){
			int y;
			cin >> y;
			Adj[y].pb(i);
		}
	}
	for(int i = 1; i <= n; i++) bfss(i);
	cout << ans + n << "\n";
}

signed main(){
	ios_base::sync_with_stdio(0);
	process();
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -