제출 #777153

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
777153		OrazB	Bosses (BOI16_bosses)	C++14	100 / 100	621 ms	2876 KiB

bosses

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
//Dijkstra->set
//set.find_by_order(x) x-position value
//set.order_of_key(x) number of strictly less elements don't need *set.??
#define N 100005
#define wr cout << "Continue debugging\n";
#define all(x) (x).begin(), (x).end()
#define ll long long int
#define pii pair <int, int>
#define pb push_back
#define ff first
#define ss second
#define pv pair<pii,vector<bool>>

int n;
vector<int> E[N];

pv F(int i, vector<bool> vis){
	int cnt = 0;
	vector<bool> nw(n+1, 0);
	queue<pii> q; q.push({i, 1});
	int sum = 0;
	while(!q.empty()){
		int x = q.front().ff, c = q.front().ss;
		q.pop();
		if (nw[x]) continue;
		nw[x] = 1;
		cnt++;
		for (auto j : E[x]) if (!nw[j] and !vis[j]) q.push({j, c+1});
		sum += c;
	}	
	return {{cnt, -sum}, nw};
}

int main ()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++){
		int k;
		cin >> k;
		while(k--){
			int x;
			cin >> x;
			E[x].pb(i);
		}
	}
	int sum = 0;
	vector<bool> vis(n+1, 0);
	while(1){
		pv mx;
		for (int i = 1; i <= n; i++){
			if (!vis[i]){
				pv X = F(i, vis);
				mx = max(mx, X);
			}
		}
		if (!mx.ff.ff) break;
		sum += -mx.ff.ss;
		vector<bool> nw = mx.ss;
		for (int i = 1; i <= n; i++){
			vis[i] = max(vis[i], nw[i]);
		}
	}
	cout << sum << '\n';
}	

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