Submission #73020

#	Time	Username	Problem	Language	Result	Execution time	Memory
73020		mraron	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	2063 ms	12252 KiB

bitaro

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
vector<int> adj[100001];
vector<int> badj[100001];
int indeg[100001];
const int BLKSZ=300;
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() {
	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]++;
	}
	
	set<pair<int,int>> st;
	for(int i=1;i<=n;++i) {
		st.insert({indeg[i], i});
	}
	
	while(!st.empty()) {
		pair<int,int> akt=*st.begin();
		st.erase(st.begin());
		
		//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());
		reverse(lst.begin(), lst.end());
		
		
		for(int i=0;i<(int)lst.size() && i<BLKSZ;++i) {
			best[akt.second].push_back(lst[i]);
		}
	
		for(auto i:adj[akt.second]) {
			auto it=st.lower_bound({indeg[i], i});
			auto val=*it;
			st.erase(it);
			
			val.first--;
			indeg[i]--;
			
			st.insert(val);
		}
	}

	
	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(best[place].size()<BLKSZ) {
			cout<<"-1\n";
			for(int i=0;i<cnt;++i) {
				bannolt[banned[i]]=0;
			}
			continue ;
		}
		
		for(int i=1;i<=n;++i) {
			dp[i]=-2;
		}
		

		cout<<dfs(place)<<"\n";
		
		for(int i=0;i<cnt;++i) {
			bannolt[banned[i]]=0;
		}
		
	}
	
	return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 86