Submission #941712

#	Time	Username	Problem	Language	Result	Execution time	Memory
941712		oblantis	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1554 ms	261500 KiB

bitaro

#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int inf = 1e9;
const int mod = 1e9+7;
const int maxn = 1e5 + 1;

vt<int> g[maxn];
vt<pii> hv[maxn];
bool was[maxn];
int dp[maxn];
void solve() {
	int n, m, q, sq;
	cin >> n >> m >> q;
	sq = sqrt(n);
	if(sq * sq != n)sq++;
	for(int i = 0, u, v; i < m; i++){
		cin >> u >> v;
		g[--v].pb(--u);
	}
	for(int i = 0; i < n; i++){
		hv[i].pb({0, i});
		for(auto k : g[i]){
			vt<pii> res;
			int j = hv[i].size() - 1, o = hv[k].size() - 1, sz = 0;
			while((j >= 0 || o >= 0) && sz < sq){
				while(j >= 0 && was[hv[i][j].ss])j--;
				while(o >= 0 && was[hv[k][o].ss])o--;
				if(j < 0 && o < 0)break;
				if(o < 0)res.pb(hv[i][j--]);
				else if(j < 0)res.pb({hv[k][o].ff + 1, hv[k][o].ss});
				else if(hv[i][j].ff > hv[k][o].ff + 1)res.pb(hv[i][j--]);
				else res.pb({hv[k][o].ff + 1, hv[k][o].ss});
				was[res.back().ss] = 1;
				sz++;
			}
			for(auto j : res)was[j.ss] = 0;
			reverse(all(res));
			hv[i] = res;
		}
	}
	for(int i = 0; i < q; i++){
		int k, t;
		cin >> t >> k;
		--t;
		vt<int> x(k);
		for(int j = 0; j < k; j++){
			cin >> x[j];
			was[--x[j]] = 1;
		}
		if(k >= sq){
			for(int j = 0; j <= t; j++){
				if(was[j])dp[j] = -inf;
				else dp[j] = 0;
				for(auto o : g[j]){
					dp[j] = max(dp[j], dp[o] + 1);
				}
			}
			if(dp[t] < 0)cout << "-1\n";
			else cout << dp[t] << '\n';
		}
		else {
			int sz = hv[t].size() - 1;
			while(sz >= 0 && was[hv[t][sz].ss]){
				sz--;
			}
			if(sz < 0)cout << "-1\n";
			else cout << hv[t][sz].ff << '\n';
		}
		for(auto j : x)was[j] = 0;
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int times = 1;
	//cin >> times;
	for(int i = 1; i <= times; i++) {
		solve();
	}
	return 0;
}

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