Submission #125135

#	Time	Username	Problem	Language	Result	Execution time	Memory
125135		miguel	Bosses (BOI16_bosses)	C++14	100 / 100	1018 ms	916 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define sz size()
#define x first
#define y second
#define pi pair <int, int>
#define pii pair <pi, int>
#define vi vector <int>
const ll mod = 1e9 + 7;
int n, q;
vector<int> g[10002];
int u[10001], d[10001];

int tst(int x){
	queue <int> q;
	for(int i=1; i<=n; i++)u[i]=0, d[i]=0;
	q.push(x);
	u[x]=1, d[x]=1;
	while(!q.empty()){
		int p=q.front();
		q.pop();
		for(int j=0; j<g[p].size(); j++){
			int i=g[p][j];
			if(u[i]==0){
				u[i]=1;
				d[i]=d[p]+1;
				q.push(i);
			}
		}
	}
	int ans=0;
	for(int i=1; i<=n; i++){
		if(u[i]==0) return -1;
		else ans+=d[i];
	}
	return ans;
}

int main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
	cin>>n;
	for(int i=1; i<=n; i++){
		int k;
		cin>>k;
		for(int j=1; j<=k; j++){
			int x;
			cin>>x;
			g[x].pb(i);
		}
	}
	int ans=1e9;
	for(int i=1; i<=n; i++){
		int cur=tst(i);
		//cout<<i<<" "<<cur<<endl;
		if(cur!=-1) ans=min(cur, ans);
	}
	if(ans!=1e9)cout<<ans<<endl;
	else cout<<-1<<endl;
}

Compilation message (stderr)

bosses.cpp: In function 'int tst(int)':
bosses.cpp:26:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<g[p].size(); j++){
                ~^~~~~~~~~~~~

• Subtask 1: 22 / 22
• Subtask 2: 45 / 45
• Subtask 3: 33 / 33