제출 #167987

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
167987		Fasho	Bosses (BOI16_bosses)	C++14	67 / 100	1578 ms	47972 KiB

bosses

#include <bits/stdc++.h>
#define N 1000005
#define ll long long int 	
#define MP make_pair
#define pb push_back
#define ppb pop_back
#define sp " "
#define endl "\n"
#define fi first
#define se second
#define ii pair<int,int>
#define lli pair<ll,ll>
#define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define fast2 freopen ("badhair.gir","r",stdin);freopen ("badhair.cik","w",stdout);
#define mod 1000000007
#define fs(x,y) for(ll i=1;i<=y;i++) cin>>x[i]
#define fo(i,x,y) for(ll i=x;i<=y;i++)
#define INF 1000000000005
using namespace std;

ll n,m,ar[N],sum=INT_MAX,t,top,vis[N],mark[N],dp[N];

vector<int> v[N],vl[N]; 

queue<lli> q;

ll f(int ind)
{
	if(vis[ind])
		return 0;
	vis[ind]++;
	ll res=0;
	for(int i=0;i<vl[ind].size();i++)
	{
		int x=vl[ind][i];
		if(!vis[x])
			res+=f(x);
	}
	return dp[ind]=res+1;
}


void bs(int st)
{
	for(int i=1;i<=n;i++)
	{
		vl[i].clear();
		vis[i]=0;
		dp[i]=0;
	}
	q.push({st,st});
	while(!q.empty())
	{
		lli x=q.front();
		q.pop();
		if(mark[x.fi])
			continue;
		// cerr<<"[d]"<<x.fi<<endl;
		mark[x.fi]=1;
		vl[x.se].pb(x.fi);
		for(int i=0;i<v[x.fi].size();i++)
		{
			int y=v[x.fi][i];
			if(!mark[y])
				q.push({y,x.fi});
		}
	}
	fo(i,1,n)
	if(!mark[i])
		return;
	f(st);
	fo(i,1,n)
	top+=dp[i];
	// cerr<<"HEL"<<endl;

}

int main()
{
	fast;
	cin>>n;
	fo(i,1,n)
	{
		cin>>m;
		fo(j,1,m)
		{
			int a;
			cin>>a;
			v[a].pb(i);
		}
	}

	for(int i=1;i<=n;i++)
	{
		top=0;
		fo(j,1,n)
			mark[j]=0;
		bs(i);
		int flag=0;
		fo(j,1,n)
			flag+=!mark[j];
		if(flag)
			continue;
		sum=min(sum,top);
	}
	cout<<sum;

}



/*     cd onedrive\desktop\kod
cls

Sinav:21-22 aralik
Aciklama: Muhtemelen 25 aralik
*/

컴파일 시 표준 에러 (stderr) 메시지

bosses.cpp: In function 'long long int f(int)':
bosses.cpp:33:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<vl[ind].size();i++)
              ~^~~~~~~~~~~~~~~
bosses.cpp: In function 'void bs(int)':
bosses.cpp:61:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<v[x.fi].size();i++)
               ~^~~~~~~~~~~~~~~

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