Submission #723593

#	Time	Username	Problem	Language	Result	Execution time	Memory
723593		Mardonbekhazratov	Bosses (BOI16_bosses)	C++17	0 / 100	1 ms	212 KiB

bosses

#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define ff first
#define ll long long
#define sd second
using namespace std;
vector<vector<int>>v,g;
vector<int>a,res;
vector<bool>vis;

void dfs(int x){
    vis[x]=true;
    int s=0;
    for(int z:g[x]){
        if(!vis[z]) dfs(z);
        s+=res[z];
    }
    res[x]+=s;
}

int main(){
	int n,x;cin>>n;
	v.resize(n+1);
	g.resize(n+1);
	res.assign(n+1,1);
	a.assign(n+1,0);
	vis.assign(n+1,false);
	set<pair<int,int>,greater<pair<int,int>>>s;
	for(int i=1;i<=n;i++){
		int k;cin>>k;
		for(int j=0;j<k;j++){
			int x;cin>>x;
			v[x].push_back(i);
			a[x]++;
		}
	}
	for(int i=1;i<=n;i++) s.insert({a[i],i});
	pair<int,int> root=*s.begin();
	x=root.sd;
	vis[x]=true;
	while(!s.empty()){
		pair<int,int> l=*s.begin();
		x=l.sd;
		if(count(all(vis),true)==n) break;
		s.erase(s.begin());
		for(int z:v[x]){
			if(!vis[z]){
				vis[z]=true;
				g[x].push_back(z);
			}
		}
	}
	//for(int i=1;i<=n;i++){for(int z:g[i]) cout<<z<<' ';cout<<endl;}
	vis.assign(n+1,false);
	for(int i=1;i<=n;i++){
	    if(!vis[i]) dfs(i);
	}
	ll c=0;
	for(int i=1;i<=n;i++) c+=res[i];
	cout<<c;
}

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