Submission #854962

#	Time	Username	Problem	Language	Result	Execution time	Memory
854962		parlimoos	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1195 ms	212308 KiB

bitaro

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

const int root = 150;

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

void init(){
	for(int i = 0 ; i < n ; i++){
		vector<int> exs;
		lps[i].push_back({0 , i});
		exs.push_back(i);
		ddd[i][0] = 0;
		ddd[i][1] = i + 1;
		
		for(int v : g[i]){
			for(pair<int , int> el : lps[v]){
				if(ddd[el.second][1] != i + 1){
					exs.push_back(el.second);
					ddd[el.second][1] = i + 1;
					ddd[el.second][0] = el.first + 1;
				}else ddd[el.second][0] = max(ddd[el.second][0] , el.first + 1);
			}
		}
		for(int el : exs){
			lps[i].push_back({ddd[el][0] , el});
		}
		sort(lps[i].begin() , lps[i].end() , greater<pair<int , int>>());
		
		int len = (int)lps[i].size();
		while(len > root){
			lps[i].pop_back();
			len--;
		}
	}
}
void bfs(int op){
	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[i] == op){
			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);
	}
	
	if(q > 1) init();
	for(int i = 0 ; i < q ; i++){
		int y;
		cin >> r >> y;
		r--;
		
		for(int j = 0 ; j < y ; j++){
			int d;
			cin >> d;
			d--;
			dels[d] = i + 1;
		}
		if(y >= root or q == 1){
			bfs(i + 1);
			cout << dis[r] << "\n";
		}else{
			int res = -1;
			for(int j = 0 ; j < (int)lps[r].size() ; j++){
				if(dels[lps[r][j].second] != i + 1){
					res = lps[r][j].first;
					break;
				}
			}
			cout << res << "\n";
		}
	}
}

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