Submission #1350677

#TimeUsernameProblemLanguageResultExecution timeMemory
1350677jumpBitaro’s Party (JOI18_bitaro)C++20
7 / 100
604 ms589824 KiB
#include <bits/stdc++.h>
#define int long long
int RANGE=300;
int n,m,q;
//int height[100010];
//std::vector<std::pair<int,int>> dpV[100010];
//std::vector<std::pair<int,int>> dpVn[100010];
int id[100010];
int dp[100010];
int tempDp[100010];
bool out[100010];
std::vector<std::pair<int,int>> res[100010];
std::vector<int> adj[100010];
std::vector<int> rev[100010];
std::vector<int> order;
bool visit[100010];
std::stack<int> st;
void dfs(int curr){
	if(visit[curr])return;
	visit[curr]=true;
	for(auto to:adj[curr]){
		dfs(to);
	}
	order.push_back(curr);
	return;
}
signed main(){
	std::ios_base::sync_with_stdio(0);std::cin.tie(0);
	std::cin >> n >> m >> q;
	RANGE=300;
	for(int i=0;i<m;i++){
		int s,e;
		std::cin >> s >> e;
		adj[s].push_back(e);
		rev[e].push_back(s);
	}
	for(int u = 1;u <= n;u++){
		for(int v : rev[u]) id[v] = 0;
		for(int j = 0;j < RANGE;j++)
		{
			std::pair<int,int> mx = {u,0};
			for(int v : rev[u]) 
			{
				while(id[v]<res[v].size() and out[res[v][id[v]].first]) id[v]++;
				if(id[v]<res[v].size() and res[v][id[v]].second+1>mx.second) mx = {res[v][id[v]].first,res[v][id[v]].second+1};
			}
			res[u].push_back(mx);
			out[mx.first] = true;
			st.push(mx.first);
			if(mx.first==u) break;
			else id[mx.first]++;
		}
		while(!st.empty()) out[st.top()] = false,st.pop();
	}
	while(q--){
		int t,y;
		std::vector<int> absent;
		std::cin >> t >> y;
		for(int i=0;i<y;i++){
			int x;
			std::cin >> x;
			out[x] = true; 
			st.push(x);
		}
		if(y>=RANGE){
			for(int i=1;i<=n;i++) dp[i] = -1e18;
			dp[t]=0;
			int ans = -1;
			if(!out[t]) ans = 0;
			for(int i = t-1;i >= 1;i--)
			{
				for(int v : adj[i]) dp[i] = std::max(dp[i],dp[v]+1);
				if(!out[i]) ans = std::max(ans,dp[i]);
			}
			std::cout << ans << '\n';
		}
		else{
			int ans = -1;
			for(auto [x,y] : res[t]) if(!out[x]){ ans = y; break; } 
			std::cout << ans << '\n';
		}
		while(!st.empty()) out[st.top()] = false,st.pop();
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...