제출 #1087288

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1087288		Gray	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	609 ms	246696 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 = 2e9;
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 append(pair<ll, ll> x, vector<pair<ll, ll>> &st){
	st.push_back(x);
}
 
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]);
	sort(dp[u].rbegin(), dp[u].rend());
	while (dp[u].size()>B) dp[u].pop_back();
	reverse(dp[u].begin(), dp[u].end());
}
 
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);
	}
	while (q--){
		ll t, y; cin >> t >> y;
		set<ll> blocked;
		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