Submission #1087402

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087402		Gray	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	405 ms	121680 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<vector<pair<ll, ll>>> dp;

multiset<pair<ll, pair<ll, ll>>, greater<pair<ll, pair<ll, ll>>>> point;
 
void dfs(ll u, vector<bool> &vis){
	vis[u]=1;
	point.clear();
	for (auto v:A[u]){
		if (!vis[v]) dfs(v, vis);
		point.insert({dp[v][0].ff, {0, v}});
	}
	// cout << u << " :-: ";
	while (!point.empty() and (ll)dp[u].size()<B){
		auto cur = *point.begin();
		// cout << cur.ff << "-" << cur.ss.ss << " ";
		point.erase(point.begin());
		dp[u].push_back({cur.ff+1, dp[cur.ss.ss][cur.ss.ff].ss});
		if (cur.ss.ff+1<(ll)dp[cur.ss.ss].size()){
			point.insert({dp[cur.ss.ss][cur.ss.ff+1].ff, {cur.ss.ff+1, cur.ss.ss}});
		}
	}
	// cout << ln;
	if ((ll)dp[u].size()<B) dp[u].push_back({0, 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);
	}
	// for (ll i=1; i<=n; i++){
	// 	cout << i << ": ";
	// 	for (auto v:dp[i]) cout << v.ff << "-" << v.ss << " ";
	// 	cout << ln;
	// }
	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