제출 #73299

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
73299		mraron	Bitaro’s Party (JOI18_bitaro)	C++14	0 / 100	19 ms	10944 KiB

bitaro

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
vector<int> adj[100001];
vector<int> badj[100001];
int indeg[100001];
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 volt[100010], voltind=0;

vector<pair<int,int>> rendez(vector<int>& miket) {
	/*for(auto i:miket) {
		cerr<<i<<" ";
	}cerr<<" RENDEZ\n";*/
	if(miket.size()==0) {
		return {};
	}
	if(miket.size()==1) {
		vector<pair<int,int>> cpy=best[miket[0]];
		for(auto& i:cpy) i.first++;
		return cpy;
	}
	
	vector<int> L, R;
	for(int i=0;i<(int)miket.size()/2;++i) {
		L.push_back(miket[i]);
	}
	
	for(int i=(int)miket.size()/2;i<(int)miket.size();++i) {
		R.push_back(miket[i]);
	}
	
	auto l=rendez(L), r=rendez(R);
	int i=0, j=0;
	
	voltind++;
	
	vector<pair<int,int>> ans;
	while((i<(int)l.size() || j<(int)r.size()) && (int)ans.size()<BLKSZ) {
		//cerr<<i<<" "<<j<<"\n";cerr.flush();
		while(i<(int)l.size() && volt[l[i].second]==voltind) i++;
		while(j<(int)r.size() && volt[r[j].second]==voltind) j++;
		
		if(i<(int)l.size() && (j==(int)r.size() || l[i]>=r[i])) {
			ans.push_back(l[i++]);
			volt[ans.back().second]=voltind;
		}else if(j<(int)r.size()) {
			ans.push_back(r[j++]);
			volt[ans.back().second]=voltind;
		}
		//cerr<<i<<" "<<j<<"\n";cerr.flush();
	}
	/*
	for(auto i:ans) {
		cerr<<i.first<<" "<<i.second<<";";
	}cerr<<"!\n";
	*/
	
	return 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});
		//cerr<<akt.second<<"==========\n";
		best[akt.second]=rendez(badj[akt.second]);
		if((int)best[akt.second].size()<BLKSZ) {
			best[akt.second].push_back({0, akt.second});
		}
		
		/*lst.push_back({0, akt.second});
		for(auto i:badj[akt.second]) {
			for(auto j:best[i]) {
				lst.push_back({j.first+1, j.second});
			}
		}
		
		sort(lst.rbegin(), lst.rend());
	
		voltind++;
		for(int i=0, j=0;i<(int)lst.size()&&j<BLKSZ;++i) {
			if(volt[lst[i].second]!=voltind) {
				volt[lst[i].second]=voltind;
				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=1;i<=n;++i) {
		cerr<<i<<": ";
		for(auto j:best[i]) {
			cerr<<j.first<<" "<<j.second<<";";
		}cerr<<"\n";
	}*/
	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;
}

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