Submission #1087372

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

bitaro

#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;
	}
}

ll brute(ll u, set<ll> &block){
	vector<ll> dp(n+1, -1);
	bdfs(u, dp, block);
	return dp[u]==-INF?-1:dp[u];
}

vector<vector<pair<ll, ll>>> dp;

void dfs(ll u, vector<ll> &vis){
	vis[u]=1;
	for (auto v:A[u]){
		if (!vis[v]) dfs(v, vis);
		if (vis[v]==1) continue;
		for (auto ch:dp[v]){
			dp[u].push_back({ch.ff+1, ch.ss});
		}
	}
	dp[u].push_back({0, u});
	sort(dp[u].rbegin(), dp[u].rend());
	while (dp[u].size()>B) dp[u].pop_back();
	vis[u]=2;
}

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<ll> vis(n+1, 0);
	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