Submission #1087388

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087388		Gray	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	2027 ms	491924 KiB

bitaro

#pragma GCC optimize("Ofast")
#pragma GCC target("sse3,avx2")
#include <bits/stdc++.h>
#define ll int
#define ld long double
#define ff first
#define ss second
#define ln "\n"
using namespace std;
 
const ll INF = INT_MAX;
const ll MOD = (ll)1e9+7;
 
const ll B = 100;
 
ll n, m, q;
vector<vector<ll>> A;
 
void bdfs(ll u, vector<ll> &dp, set<ll> &blocked){
	dp[u]=0;
	for (auto v:A[u]){
		if (dp[v]==-1){
			bdfs(v, dp, blocked);
		}
		dp[u]=max(dp[u], dp[v]+1);
	}
	if (dp[u]==0 and blocked.count(u)){
		dp[u]=-INF;
	}
}
vector<ll> idp;
ll brute(ll u, set<ll> &block){
	idp.assign(n+1, -1);
	bdfs(u, idp, block);
	return idp[u]==-INF?-1:idp[u];
}

vector<set<pair<ll, ll>>> dp;
 
void append(pair<ll, ll> x, set<pair<ll, ll>> &st){
	st.insert(x);
	while (st.size()>B) st.erase(*st.begin());
}
 
void dfs(ll u, vector<bool> &vis){
	vis[u]=1;
	for (auto v:A[u]){
		if (!vis[v]) dfs(v, vis);
		for (auto ch:dp[v]){
			append({ch.ff+1, ch.ss}, dp[u]);
		}
	}
	append({0, u}, dp[u]);
}
 
void solve(){
	cin >> n >> m >> q;
	A.resize(n+1);
	for (ll i=0; i<m; i++){
		ll u, v; cin >> u >> v;
		A[v].push_back(u);
	}
	dp.resize(n+1);
	vector<bool> vis(n+1);
	for (ll i=1; i<=n; i++){
		if (!vis[i]) dfs(i, vis);
	}
	set<ll> blocked;
	while (q--){
		ll t, y; cin >> t >> y;
		blocked.clear();
		for (ll i=0; i<y; i++){
			ll x; cin >> x; blocked.insert(x);
		}
		if (y<B){
			ll mx=-1;
			for (auto ch:dp[t]){
				if (!blocked.count(ch.ss)) mx=max(mx, ch.ff);
			}
			cout << mx << ln;
		}else{
			cout << brute(t, blocked) << ln;
		}
	}
}
 
 
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(nullptr);
	ll t=1;
	// cin >> t;
	while (t--) solve();
}

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