Submission #1234248

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234248		hashdfdfh	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	915 ms	216368 KiB

bitaro

#include <bits/stdc++.h>
#define mid ((l+r)>>1)
using namespace std;
vector<int> vc[200005];
vector<pair<int,int>> nr[200005];
int B=150;
int ok[200005],dist[200005],tag[200005];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
	int n,m,q; cin>>n>>m>>q;
	for(int i=1;i<=m;i++){
		int u,v; cin>>u>>v;
		vc[u].push_back(v);
	}
	for(int i=1;i<=n;i++){
		if(nr[i].size()<B){
			nr[i].push_back(make_pair(0,i));
		}
		for(auto v:vc[i]){
			vector<pair<int,int>> nw;
			int it1=0,it2=0;
			while(((it1!=nr[i].size())||(it2!=nr[v].size()))&&(nw.size()<B)){
				if(it1==nr[i].size()){
					if(tag[nr[v][it2].second]){
						it2++;
						continue; 
					}  tag[nr[v][it2].second]=1;
					nw.push_back(nr[v][it2]);
					it2++;
					continue;
				}
				if(it2==nr[v].size()){
					if(tag[nr[i][it1].second]){
						it1++;
						continue; 
					} tag[nr[i][it1].second]=1;
					auto t=nr[i][it1];
					t.first++;
					nw.push_back(t);
					it1++;
					continue;
				}
				if(nr[i][it1].first+1>nr[v][it2].first){
					if(tag[nr[i][it1].second]){
						it1++; 
						continue; 
					} tag[nr[i][it1].second]=1;
					auto t=nr[i][it1];
					t.first++;
					nw.push_back(t);
					it1++;
					continue;
				}
				else{
					if(tag[nr[v][it2].second]){
						it2++; 
						continue; 
					} tag[nr[v][it2].second]=1;
					nw.push_back(nr[v][it2]);
					it2++;
					continue;
				}
			}
			swap(nw,nr[v]);
			nw.clear();
			for(auto u:nr[v]) tag[u.second]=0;
		}
	}
//	for(int i=1;i<=n;i++,cout<<"\n") for(auto v:nr[i]) cout<<v.first<<" "<<v.second<<"  ";
	while(q--){
		int s,k; cin>>s>>k;
		if(k>=150){
			for(int i=1;i<=n;i++) ok[i]=1,dist[i]=-1;
			while(k--){
				int x; cin>>x; ok[x]=0;
			}
			for(int i=1;i<=n;i++){
				if(ok[i]) dist[i]=max(dist[i],0);
				if(dist[i]>=0){
					for(auto v:vc[i]){
						dist[v]=max(dist[v],dist[i]+1);
					}
				}
			}
			cout<<dist[s]<<"\n";
		}
		else{
			vector<int> nd;
			while(k--){
				int x; cin>>x; nd.push_back(x);
			}
			for(auto v:nd) tag[v]=1;
			int maxv=-1;
			for(auto v:nr[s]){
				if(!tag[v.second]){
					maxv=v.first;
					break;
				}
			}
			for(auto v:nd) tag[v]=0;
			cout<<maxv<<"\n"; 
		}
	} 
	return 0;
} 

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