Submission #1087411

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087411		Gray	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1424 ms	476592 KiB

bitaro

// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse3,avx2")
#include <bits/stdc++.h>
#define ll long long
#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;

set<pair<ll, pair<ll, ll>>, greater<pair<ll, pair<ll, ll>>>> point;
vector<bool> usd;

void dfs(ll u, vector<bool> &vis){
	vis[u]=1;
	point.clear();
	for (auto v:A[u]){
		if (!vis[v]) dfs(v, vis);
		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());
	vector<pair<ll, ll>> real;
	for (auto ch:dp[u]){
		if (!usd[ch.ss]) {real.push_back(ch); usd[ch.ss]=1;}
	}
	for (auto ch:real) usd[ch.ss]=0;
	dp[u]=real;
	while (dp[u].size()>B) dp[u].pop_back();
}
 
void solve(){
	cin >> n >> m >> q;
	A.resize(n+1);
	usd.assign(n+1, 0);
	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: 86 / 86