Submission #1269752

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269752		WH8	Bitaro’s Party (JOI18_bitaro)	C++20	14 / 100	2095 ms	13048 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, -2);

int slow(int x){
	if(mem[x]!=-2)return mem[x];
	if(exist[x])mem[x]=0;
	else mem[x]=-1;
	for(auto it:fro[x]){
		int ret=slow(it);
		//~ printf("at x %lld, from it %lld, ret is %lld\n", x, it, ret);
		if(ret != -1)mem[x]=max(mem[x], ret+1);
	}
	return mem[x];
}

signed main(){
	cin>>n>>m>>q;
	for(int i=0;i<m;i++){
		int a,b;cin>>a>>b;
		assert(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(),-2);
			cout<<slow(t)<<"\n";
		//~ }
		//~ for(int i=1;i<=n;i++){
			//~ cout<<mem[i]<<" ";
		//~ }
		//~ cout<<endl;
		for(auto it:blocked){
			exist[it]=1;
		}
	}
	
}

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