oj.uz

Submission #838897

# Submission time Handle Problem Language Result Execution time Memory
838897 2023-08-28T05:40:47 Z vjudge1 Bosses (BOI16_bosses) C++17
22 / 100
 1 ms 468 KB 
/*#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);
	used[pos]=1;
	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

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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Incorrect 1 ms 468 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Incorrect 1 ms 468 KB Output isn't correct
8 Halted 0 ms 0 KB -