Submission #930516

#	Time	Username	Problem	Language	Result	Execution time	Memory
930516		iskhakkutbilim	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1188 ms	421072 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int N = 1e5;
const int SZ = 400;
vector<int> g[N+5], gg[N+5];
vector<pair<int,int> > calc[N+1];
signed main(){
   ios::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);
	int n, m, q; cin >> n >> m >> q;
	for(int i = 0;i < m; i++){
		int a, b; cin >> a >> b;
		g[a].push_back(b);
		gg[b].push_back(a);
	}
	
	
	vector<int> reach, dist(n+1), last(n+1, 0);
	for(int i = 1;i <= n; i++){
		reach.push_back(i);
		for(auto to : gg[i]){
			for(auto [d, u] : calc[to]){
				if(last[u] == i){
					dist[u] = max(dist[u], d + 1);
				}else{
					dist[u] = d + 1;
					last[u] = i;
					reach.push_back(u);
				}
			}
		}
		sort(all(reach),[&](int a, int b){
			return dist[a] > dist[b];
		});
		for(int j = 0;j < min(SZ, (int)reach.size()); j++){
			calc[i].push_back({dist[reach[j]], reach[j]});
		}
		reach.clear();
	}
	
	
	
	int timer = 1;
	vector<int> del(n+1, 0);
	while(q--){
		int v, k; cin >> v >> k;
		for(int i = 0;i < k; i++){
			int x; cin >> x;
			del[x] = timer;
		}
		
		
		if(k < SZ){
			int ans = -1;
			for(auto [d, u] : calc[v]){
				if(del[u] != timer){
					ans = d;
					break;
				}
			}
			cout << ans << '\n';
		}else{
			vector<int> d(n+1, -1);
			
			for(int i = 1;i <= n; i++){				
				if(del[i] != timer){
					d[i] = max(d[i], 0);
				}
				for(int to : g[i]){
					if(d[i] != -1)
					d[to] = max(d[to], d[i] + 1);
				}
			}
			cout << d[v] << '\n';
		}
		
		
		
		
		timer++;
	}
	
	
	
	return 0;
}

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