Submission #765903

#	Time	Username	Problem	Language	Result	Execution time	Memory
765903		minhcool	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1590 ms	191880 KiB

bitaro

#define local
#ifndef local
#include ""
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 3e5 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

mt19937 rng(1);

int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}

int n, m, q;

const int S = 105;

ii mx[N][S];

int itr[N];
bool ck[N], ck2[N], vis[N];

vector<int> lst[N], nxt[N];

int len[N];

#ifdef local
void process(){
	cin >> n >> m >> q;
	for(int i = 1; i <= m; i++){
		int x, y;
		cin >> x >> y;
		lst[y].pb(x);
		nxt[x].pb(y);
	}
	for(int i = 1; i <= n; i++){
		vector<ii> vc;
		for(auto it : lst[i]){
			//cout << "EDGE " << i << " " << it << "\n";
			//cout << mx[i][j].se << "\n";
			for(int j = 1; j <= 100; j++) vc.pb({mx[it][j].fi + 1, mx[it][j].se});
			//vc.pb({1, it});
		}
		//for(auto it : vc) cout << "OK " << it.fi << " " << it.se << "\n";
		sort(vc.begin(), vc.end(), greater<ii>());
		int itr = 0;
		for(auto it : vc){
			//cout << it.se << "\n";
			if(vis[it.se]) continue;
		//	cout << "OKAY " << it.fi << " " << it.se << "\n";
			itr++;
			if(itr > 100) break;
			vis[it.se] = 1;
			mx[i][itr] = it;
		}
	//	cout << i << " " << itr << "\n";
		if(itr < 100){
			itr++;
			mx[i][itr] = {0, i};
		}
		for(int j = 1; j <= 100; j++) vis[mx[i][j].se] = 0;
	//	cout << i << " ";
	//	for(int j = 1; j <= itr; j++) cout << mx[i][j].fi << " " << mx[i][j].se << " ";
	//	cout << "\n";
		//priority_queue<ii, vector<ii>, greater<ii>> pq;
	}
	while(q--){
		int s, x;
		cin >> s >> x;
		vector<int> vc;
		for(int i = 1; i <= x; i++){
			int y;
			cin >> y;
			vc.pb(y);
			ck2[y] = 1;
		}
		int answer = -1;
		for(int i = 1; i <= 100; i++){
			if(mx[s][i].se == 0) continue;
			if(!ck2[mx[s][i].se]){
				answer = mx[s][i].fi;
				break;
			}
		}
		if(answer < 0){
			for(int i = 1; i <= n; i++) len[i] = -oo;
			len[s] = 0;
			for(int i = s - 1; i >= 1; i--){
				for(auto it : nxt[i]) len[i] = max(len[i], len[it] + 1);
			}
			for(int i = 1; i <= s; i++) if(!ck2[i]) answer = max(answer, len[i]);
		}
		for(auto it : vc) ck2[it] = 0;
		cout << answer << "\n";
	}
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	process();
}
#endif

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 86 / 86