oj.uz

Submission #112651

# Submission time Handle Problem Language Result Execution time Memory
112651 2019-05-21T07:30:58 Z Evirir Bosses (BOI16_bosses) C++17
100 / 100
 1455 ms 1244 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define watch(x) cout<<(#x)<<"="<<(x)<<endl
#define mset(d,val) memset(d,val,sizeof(d))
#define setp(x) cout<<fixed<<setprecision(x)
#define forn(i,a,b) for(int i=a;i<b;i++)
#define fore(i,a,b) for(int i=a;i<=b;i++)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define PI 3.14159265358979323846264338327
#define INF 2e14
#define MOD 998244353
#define pqueue priority_queue
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef unsigned long long ull;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;

#define MAXN 5005

int n;
vi adj[MAXN];
vi adj2[MAXN];
bool vst[MAXN];
ll sz[MAXN];
ll cnt=0;

void bfs(int r){
	queue<int> q;
	q.push(r);
	vst[r]=true;
	cnt++;
	
	while(!q.empty()){
		int u=q.front(); q.pop();
		for(int v: adj[u]){
			if(!vst[v]){
				adj2[u].pb(v);
				q.push(v);
				vst[v]=true;
				cnt++;
			}
		}
	}
	//cout<<'\n';
}

void dfs(int u){
	sz[u]=1;
	for(int v: adj2[u]){
		dfs(v);
		sz[u]+=sz[v];
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	cin>>n;
	forn(i,0,n){
		int t; cin>>t;
		forn(j,0,t){
			int u; cin>>u; u--;
			adj[u].pb(i);
		}
	}
	
	ll ans=INF;
	forn(i,0,n){
		mset(vst,0);
		mset(sz,0);
		cnt=0;
		forn(j,0,n) adj2[j].clear();
		
		bfs(i);
		
		/*forn(i,0,n){
			cout<<"adj["<<i+1<<"]: ";
			for(int v: adj2[i]) cout<<v+1<<" ";
			cout<<'\n';
		}*/
		
		if(cnt!=n) continue;
		
		dfs(i);
		
		ll sum=0;
		forn(j,0,n){
			sum+=sz[j];
		}
		ans=min(ans,sum);
	}
	
	cout<<ans<<'\n';
	
	return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 2 ms 768 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 3 ms 640 KB Output is correct
11 Correct 3 ms 640 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 2 ms 768 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 3 ms 640 KB Output is correct
11 Correct 3 ms 640 KB Output is correct
12 Correct 8 ms 896 KB Output is correct
13 Correct 6 ms 876 KB Output is correct
14 Correct 200 ms 1116 KB Output is correct
15 Correct 40 ms 888 KB Output is correct
16 Correct 767 ms 1144 KB Output is correct
17 Correct 1405 ms 1244 KB Output is correct
18 Correct 1455 ms 1116 KB Output is correct