Submission #1269740

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269740		WH8	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	7 ms	6868 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;

#define int long long 
#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'

const int blk=300;

int n,m,q;
vector<vector<pll>> best(100005);
vector<vector<int>> fro(100005);

vector<bool> exist(100005, 1);
vector<int> mem(100005, -1);

int slow(int x){
	if(mem[x]!=-1)return x;
	for(auto it:fro[x]){
		mem[x]=max(mem[x], slow(it));
	}
	if(mem[x]!=-1)mem[x]+=1;
	else if(mem[x]==-1 and exist[x])mem[x]=0;
	return mem[x];
}

signed main(){
	cin>>n>>m>>q;
	for(int i=0;i<m;i++){
		int a,b;cin>>a>>b;
		fro[b].pb(a);
	}
	//~ for(int i=1;i<=n;i++){
		//~ best[i][0]={0, i};
	//~ }
	for(int i=1;i<=n;i++){
		// calculate best (max distance to) 300 nodes.
		map<int,int> m;
		m[i]=0;
		for(auto it:fro[i]){
			for(auto [node,dist] : best[it]){
				m[node]=max(m[node], dist+1);
			}
		}
		int cnt=0;
		for(auto [node, dist]:m){
			if(cnt >= blk) break;
			//~ printf("i %lld, node %lld, dist %lld\n", i, node, dist);
			best[i].pb({node, dist});
			cnt++;
		}
	}
	while(q--){
		int t,y;cin>>t>>y;
		vector<int> blocked;
		for(int i=0;i<y;i++){
			int c;cin>>c;
			exist[c]=0;
			blocked.pb(c);
		}
		if(y<blk){
			// go thru best[t]
			for(int i=0;i<(int)best[t].size();i++){
				auto [node, dist]=best[t][i];
				if(exist[node]){
					//~ printf("%lld best of t %lld is %lld and it exists\n", i,t,best[t][i].s);
					cout<<dist<<"\n";
					break;
				}
				if(i==(int)best[t].size()-1){
					cout<<-1<<"\n";
				}
			}
		}
		else {
			fill(mem.begin(),mem.end(),-1);
			cout<<slow(y)<<"\n";
		}
		for(auto it:blocked){
			exist[it]=1;
		}
	}
	
}

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