Submission #839204

#TimeUsernameProblemLanguageResultExecution timeMemory
839204vjudge1Bosses (BOI16_bosses)C++17
0 / 100
1 ms468 KiB
/*#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx,avx2,fma")*/
#include <bits/stdc++.h>
using namespace std;
#define ll int
ll n,m,k,cnt;
vector<ll>v[5001];
vector<ll>g[5001];
bool used[5001];
ll ans[5001];
bool was[5001];
void dfs(ll x)
{
	//cout<<x<<":";
	ans[x]=1;
	was[x]=1;
	for(int it:g[x])
	{
		if(!was[it])
		{
			dfs(it);
			ans[x]+=ans[it];
		}
	}
}
void anomalous_solve()
{
    cin>>n;
    ll x;
    for(int i=1;i<=n;i++)
    {
    	cin>>k;
    	for(int j=1;j<=k;j++)
    	{
    		cin>>x;
    		v[x].push_back(i);
		}
	}
	ll answer=0;
	queue<ll>q;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			used[j]=was[j]=1;
			g[j].clear();ans[j]=0;
		}
		q.push(i);
		used[i]=1;
		while(q.size()>0)
		{
			ll x=q.front();
			for(int it:v[x])
			{
				if(!used[it])
				{
					g[x].push_back(it);// dobei etot kod!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
					q.push(it);
					used[it]=1;
				}
			}
			q.pop();
		}
		dfs(i);
		cnt=0;
		for(int j=1;j<=n;j++)
		{
			cnt+=ans[j];
			if(ans[j]==0)ans[j]=1e9;
		}
		cout<<i<<" "<<answer<<"\n";
		answer=max(answer,cnt);
	}
	cout<<answer;
}
int main()
{
	//	freopen("INPUT.txt","r",stdin);
	//  freopen("OUTPUT.txt","w",stdout);

	ios_base::sync_with_stdio();
    cin.tie(NULL);
    cout.tie(NULL);

    ll test=1;
	//cin>>test;
    for(int pos=1;pos<=test;pos++)
    	anomalous_solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...