제출 #1269762

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1269762		WH8	Bitaro’s Party (JOI18_bitaro)	C++20	14 / 100	972 ms	214936 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=100;

int n,ed,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.tie(0);
	ios::sync_with_stdio(0);
	cin>>n>>ed>>q;
	for(int i=0;i<ed;i++){
		int a,b;cin>>a>>b;
		assert(a<b);
		fro[b].pb(a);
	}

	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);
			}
		}
		//~ cout<<i<<endl;
		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]
			int res=-1;
			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);
					res=dist;
					break;
				}
			}
			cout<<res<<'\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