Submission #854910

#	Time	Username	Problem	Language	Result	Execution time	Memory
854910		parlimoos	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	2062 ms	22636 KiB

bitaro

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

const int root = 320;

int n , m , q , r;
vector<int> g[100000];
set<pair<int , int>> lps[100000];
unordered_set<int> dels;
int dis[100000];

void init(){
	for(int i = 0 ; i < n ; i++){
		lps[i].insert({0 , i});
		for(int v : g[i]){
			for(pair<int , int> el : lps[v]){
				lps[i].insert({el.first + 1 , el.second});
				if((int)lps[i].size() > root){
					lps[i].erase(lps[i].begin());
				}
			}
		}
	}
}
void bfs(int v){
	fill(&dis[0] , &dis[100000] , 0);
	for(int i = 0 ; i <= r ; i++){
		for(int u : g[i]){
			dis[i] = max(dis[u] + 1 , dis[i]);
		}
		if(dis[i] == 0 and dels.find(i) != dels.end()){
			dis[i] = -1;
		}
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> m >> q;
	for(int i = 0 ; i < m ; i++){
		int v , u;
		cin >> v >> u;
		v-- , u--;
		g[u].push_back(v);
	}
	
	init();
	for(int i = 0 ; i < q ; i++){
		int y;
		cin >> r >> y;
		r--;
		dels.clear();
		
		for(int j = 0 ; j < y ; j++){
			int d;
			cin >> d;
			d--;
			dels.insert(d);
		}
		if(y >= root){
			bfs(r);
			cout << dis[r] << "\n";
		}else{
			int res = -1;
			for(pair<int , int> el : lps[r]){
				if(dels.find(el.second) == dels.end()){
					res = el.first;
				}
			}
			cout << res << "\n";
		}
	}
}

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