Submission #838890

#	Time	Username	Problem	Language	Result	Execution time	Memory
838890		vjudge1	Bosses (BOI16_bosses)	C++17	22 / 100	1 ms	516 KiB

bosses

/*#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 mx=0,pos=-1;
	for(int i=1;i<=n;i++)
	{
		//cout<<i<<":"<<v[i].size()<<"\n";
		if(v[i].size()>mx)
		{
			mx=v[i].size();pos=i;
		}
	}
	queue<ll>q;
	q.push(pos);
	while(q.size()>0)
	{
		ll x=q.front();
		for(int it:v[x])
		{
			if(!used[it])
			{
				g[x].push_back(it);
				q.push(it);
				used[it]=1;
			}
		}
		q.pop();
	}
	dfs(pos);
	for(int i=1;i<=n;i++)
	{
		cnt+=ans[i];
		//cout<<ans[i]<<" ";
	}
	cout<<cnt;
}
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();
}

Compilation message (stderr)

bosses.cpp: In function 'void anomalous_solve()':
bosses.cpp:44:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |   if(v[i].size()>mx)
      |      ~~~~~~~~~~~^~~

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