Submission #1248167

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248167		g4yuhg	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1062 ms	149636 KiB

bitaro

//Huyduocdithitp
#include <bits/stdc++.h>
typedef int ll;
#define pii pair<ll, ll> 
#define fi first
#define se second
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);
#define N 100005
#define endl '\n'
using namespace std;
 
bool ghuy4g;

const ll inf = 1e9;

const ll S = 100;

ll n, m, q, c[N], d[N], dp[N];

ll p[N][2];

vector<ll> adj[N], adj_2[N];

vector<pii> vt[N]; // vt[u][0] la con {len, u} xa nhat 

void pre() {
	/*for (int u = 1; u <= n; u ++) {
		gp_hash_table<ll, ll> mp;
		for (auto v : adj_2[u]) {
			for (auto it : vt[v]) {
				mp[it.se] = max(mp[it.se], it.fi + 1);
			}
		}
		vt[u].push_back({0, u});
		for (auto it : mp) {
			vt[u].push_back({it.se, it.fi});
		}
		//sort(vt[u].begin(), vt[u].end(), greater<pii>());
		if (vt[u].size() > S + 1) {
			partial_sort(vt[u].begin(), vt[u].begin() + S + 1, vt[u].end(), greater<pii>());
		}
		else {
			sort(vt[u].begin(), vt[u].end(), greater<pii>());
		}
		//partial_sort(a.begin(), a.begin() + S, a.end(), cmp);
    	//a.resize(S);
		if (vt[u].size() > S + 1) {
			vt[u].resize(S + 1);
		}
	}*/
	
	for (int u = 1; u <= n; u ++) {
		vector<ll> exs;
		for (auto v : adj_2[u]) {
			for (auto it : vt[v]) {
				if (p[it.se][1] != u) {
					p[it.se][1] = u;
					p[it.se][0] = it.fi + 1;
					exs.push_back(it.se);
				}
				else {
					p[it.se][0] = max(p[it.se][0], it.fi + 1);
				}
			}
		}
		vt[u].push_back({0, u});
		for (auto it : exs) {
			vt[u].push_back({p[it][0], it});
		}
		//sort(vt[u].begin(), vt[u].end(), greater<pii>());
		if (vt[u].size() > S + 1) {
			partial_sort(vt[u].begin(), vt[u].begin() + S + 1, vt[u].end(), greater<pii>());
		}
		else {
			sort(vt[u].begin(), vt[u].end(), greater<pii>());
		}
		//partial_sort(a.begin(), a.begin() + S, a.end(), cmp);
    	//a.resize(S);
		if (vt[u].size() > S + 1) {
			vt[u].resize(S + 1);
		}
	}
}

bool is[N];

void solve1(ll u, ll k) {
	for (int i = 1; i <= k; i ++) {
		cin >> d[i];
		is[d[i]] = 1;
	}
	
	ll ans = -1;
	
	for (int i = 0; i < (ll)vt[u].size(); i ++) {
		if (is[vt[u][i].se] == 0) {
			ans = max(ans, vt[u][i].fi);
			// break;
		}
	}
	
	//if (ans == 0) ans --;
	cout << ans << endl;
	
	for (int i = 1; i <= k; i ++) {
		is[d[i]] = 0;
	}
}

void solve2(ll u, ll k) {
	for (int i = 1; i <= k; i ++) {
		cin >> d[i];
		is[d[i]] = 1;
	}
	
	dp[u] = 0;
	for (int i = u - 1; i >= 1; i --) {
		dp[i] = -inf;
		for (auto v : adj[i]) {
			if (v > u) continue;
			dp[i] = max(dp[i], dp[v] + 1);
		}
	}
	
	ll ans = -1;
	
	for (int i = 1; i <= u; i ++) {
		if (is[i]) continue;
		ans = max(ans, dp[i]);
	}
	
	cout << ans << endl;
	
	for (int i = 1; i <= k; i ++) {
		is[d[i]] = 0;
	}
}

void solve() {
	for (int i = 1; i <= q; i ++) {
		ll u, yj;
		cin >> u >> yj;
		if (yj <= S) {
			solve1(u, yj);
		}
		else {
			solve2(u, yj);
		}
	}
}
 
bool klinh;
 
signed main(void) {
	faster;
	
	cin >> n >> m >> q;
	
	for (int i = 1; i <= m; i ++) {
		ll u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj_2[v].push_back(u);
	}
	
	pre();
	//return 0;
	solve();
		
	cerr << fabs(&klinh - &ghuy4g) / 1048576.0;
	return 0;
}

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