제출 #73076

#제출 시각아이디문제언어결과실행 시간메모리
73076mraronBitaro’s Party (JOI18_bitaro)C++14
14 / 100
2033 ms71568 KiB
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
vector<int> adj[100001];
vector<int> badj[100001];
int indeg[100001];
int BLKSZ=50;
vector<pair<int,int>> best[100001];
int dp[100010];
int bannolt[100010];

int dfs(int x) {
	if(dp[x]!=-2) {
		return dp[x];
	}
	
	int ans=-1;
	if(!bannolt[x]) {
		ans=0;
	}
	
	for(auto i:badj[x]) {
		if(dfs(i)>=0) {
			ans=max(ans, dfs(i)+1);
		}
	}
	
//	cerr<<x<<"->"<<ans<<" | "<<bannolt[x]<<"\n";
	
	return dp[x]=ans;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,m,q;
	cin>>n>>m>>q;
	for(int i=0;i<m;++i) {
		int a,b;
		cin>>a>>b;
		adj[a].pb(b);
		badj[b].pb(a);
		indeg[b]++;
	}
	
	vector<pair<int,int>> st;
	for(int i=1;i<=n;++i) {
		if(indeg[i]==0) st.push_back({indeg[i], i});
	}
			
		

	while(!st.empty()) {
		pair<int,int> akt=st.back();
		st.pop_back();
		
		//priority_queue<pair<int,int>> pq; //(dist, honnan)
		//pq.push({0, akt.second});
		map<int,int> mx;
		mx[akt.second]=0;
		for(auto i:badj[akt.second]) {
			for(auto j:best[i]) {
				mx[j.second]=max(mx[j.second], j.first+1);
			}
		}
		
		vector<pair<int,int>> lst;
		for(auto i:mx) {
			lst.push_back({i.second, i.first});
		}
		
		sort(lst.begin(), lst.end());		
		
		for(int i=(int)lst.size()-1, j=0;i>=0 && j<BLKSZ;--i, j++) {
			best[akt.second].push_back(lst[i]);
		}
	
		for(auto i:adj[akt.second]) {
			indeg[i]--;
	
			if(indeg[i]==0) st.pb({indeg[i], i});
		}
	}
	
	
	for(int i=0;i<q;++i) {
		int place;
		int cnt;
		cin>>place>>cnt;
		vector<int> banned(cnt);
		
		for(int i=0;i<cnt;++i) {
			cin>>banned[i];
			bannolt[banned[i]]=1;
		}
		
		bool ok=false;
		for(int j=0;j<(int)best[place].size();++j) {
			if(!bannolt[best[place][j].second]) {
				ok=true;
				cout<<best[place][j].first<<"\n";
				break ;
			}
		}
		
		if(ok) {
			for(int i=0;i<cnt;++i) {
				bannolt[banned[i]]=0;
			}
			continue ;
		}else if((int)best[place].size()<BLKSZ) {
			cout<<"-1\n";
			for(int i=0;i<cnt;++i) {
				bannolt[banned[i]]=0;
			}
			continue ;
		}
		
		for(int i=1;i<=place;++i) {
			dp[i]=-2;
		}
		

		cout<<dfs(place)<<"\n";
		
		for(int i=0;i<cnt;++i) {
			bannolt[banned[i]]=0;
		}
		
	}
	
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...