Submission #856662

#	Time	Username	Problem	Language	Result	Execution time	Memory
856662		GoldLight	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1548 ms	412400 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
void fast(){ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);}

const int SQR=300;
int main(){
	fast();
	int n, m, q; cin>>n>>m>>q;
	vector<int> v[n+1];
	for(int i=1; i<=m; i++){
		int x, y; cin>>x>>y;
		v[y].push_back(x);
	}
	vector<pair<int,int>> l[n+1]; //longest paths
	vector<int> dp(n+1), vis(n+1), block(n+1), dist(n+1), st;
	for(int i=1; i<=n; i++){
		l[i].push_back({0, i});
		for(auto j:v[i]){
			for(auto [d, x]:l[j]){
				if(vis[x]==i){
					dist[x]=max(dist[x], d+1);
				}
				else{
					dist[x]=d+1;
					vis[x]=i;
					st.push_back(x);
				}
			}
		}
		while(!st.empty()){
			int u=st.back(); st.pop_back();
			l[i].push_back({dist[u], u});
		}
		sort(l[i].begin(), l[i].end(), greater<pair<int,int>>());
		if((int)l[i].size()>SQR) l[i].erase(l[i].begin()+SQR, l[i].end());
	}
	while(q--){
		int t, y; cin>>t>>y;
		for(int i=1; i<=y; i++){
			int x; cin>>x;
			block[x]=q+1;
		}
		if(y<SQR){
			int ans=-1;
			for(auto [d, x]:l[t]){
				if(block[x]!=q+1){
					ans=d;
					break;
				}
			}
			cout<<ans<<'\n';
		}
		else{
			fill(dp.begin(), dp.end(), -1);
			for(int i=1; i<=n; i++){
				if(block[i]!=q+1){
					dp[i]=0;
				}
				for(auto j:v[i]){
					if(dp[j]!=-1) dp[i]=max(dp[i], dp[j]+1);
				}
			}
			cout<<dp[t]<<'\n';
		}
	}
}
/*
const int N=1e6, SQR=1e3;
int l[N+1], r[N+1], id[N+1];
bool cmp(int x, int y){
	if(l[x]/SQR!=l[y]/SQR) return l[x]/SQR<l[y]/SQR;
	if((l[x]/SQR)&1) return r[x]<r[y];
	return r[x]>r[y];
}
int main(){
	fast();
	int n; cin>>n;
	for(int i=1; i<=n; i++){
		cin>>l[i]>>r[i];
		id[i]=i;
	}
	sort(id+1, id+n+1, cmp);
	// for(int i=1; i<=n; i++){
	// 	cout<<l[id[i]]<<' '<<r[id[i]]<<'\n';
	// }
	// int ans=0;
	// for(int i=2; i<=n; i++){
	// 	int j=id[i], k=id[i-1];
	// 	ans+=abs(l[j]-l[k])+abs(r[j]-r[k]);
	// }
	// cout<<ans;
	for(int i=1; i<=n; i++) cout<<id[i]<<' ';
}
*/
/*
const int N=2e5, SQR=300;
int l[N+1], r[N+1], id[N+1];
bool cmp(int x, int y){
	if(l[x]/SQR!=l[y]/SQR) return l[x]/SQR<l[y]/SQR;
	return r[x]<r[y];
}
int now, a[N+1];
map<int,int> mp;
void add(int x){
	mp[a[x]]++;
	if(mp[a[x]]==1) now++;
}
void del(int x){
	mp[a[x]]--;
	if(mp[a[x]]==0) now--;
}
int main(){
	fast();
	int n, q; cin>>n>>q;
	for(int i=1; i<=n; i++) cin>>a[i];
	for(int i=1; i<=q; i++){
		cin>>l[i]>>r[i];
		id[i]=i;
	}
	sort(id+1, id+q+1);
	int ki=1, ka=0, ans[q+1];
	for(int i=1; i<=q; i++){
		int j=id[i];
		while(ki>l[j]){
			ki--;
			add(ki);
		}
		while(ka<r[j]){
			ka++;
			add(ka);
		}
		while(ki<l[j]){
			del(ki);
			ki++;
		}
		while(ka>r[j]){
			del(ka);
			ka--;
		}
		ans[j]=now;
	}
	for(int i=1; i<=q; i++) cout<<ans[i]<<'\n';
}
*/

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