제출 #1344347

#제출 시각아이디문제언어결과실행 시간메모리
1344347jumpBitaro’s Party (JOI18_bitaro)C++20
0 / 100
1 ms344 KiB
#include <bits/stdc++.h>
#define int long long
int RANGE=100000;
int n,m,q;
int height[100010];
std::vector<std::pair<int,int>> dpV[100010];
int dp[100010];
int tempDp[100010];
std::vector<int> adj[100010];
std::vector<int> order;
bool visit[100010];
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::cin >> n >> m >> q;
	RANGE=std::sqrt(100000);
	for(int i=0;i<m;i++){
		int s,e;
		std::cin >> s >> e;
		adj[s].push_back(e);
	}
	for(int i=1;i<=n;i++){
		dfs(i);
	}
	std::reverse(order.begin(),order.end());
	for(auto curr:order){
		dpV[curr].push_back({0,curr});
		std::sort(dpV[curr].rbegin(),dpV[curr].rend());
		while(dpV[curr].size()>RANGE)dpV[curr].pop_back();
		for(auto to:adj[curr]){
			for(auto [value,from]:dpV[curr]){
				dpV[to].push_back({value+1,from});
			}
			dpV[to].push_back({1,curr});
			dp[to]=std::max(dp[to],dp[curr]+1);
		}
	}
	while(q--){
		int t,y;
		std::vector<int> absent;
		std::cin >> t >> y;
		if(y==0){
			std::cout << dp[t];
			continue;
		}
		for(int i=0;i<y;i++){
			int yin;
			std::cin >> yin;
			absent.push_back(yin);
		}
		int ans=-1;
		for(auto [num,from]:dpV[t]){
			auto itr = std::lower_bound(absent.begin(),absent.end(),from);
			if(itr==absent.end()||*itr!=from){
				ans = num;
				break;
			}
		}
		if(ans!=-1){
			std::cout << ans << '\n';
			continue;
		}
		for(int i=0;i<=n;i++){
			auto itr = std::lower_bound(absent.begin(),absent.end(),i);
			if(itr==absent.end()||*itr!=i)
			tempDp[i]=0;
			else
			tempDp[i]=-1e9;
		}
		for(auto curr:order){	
			for(auto to:adj[curr]){
				dp[to]=std::max(dp[to],dp[curr]+1);
			}
		}
		dp[t]=std::max((int)(-1),dp[t]);
		std::cout << dp[t] << '\n';
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...