Submission #854930

#	Time	Username	Problem	Language	Result	Execution time	Memory
854930		parlimoos	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	1786 ms	501148 KiB

bitaro

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

const int root = 400;

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

void init(){
	for(int i = 0 ; i < n ; i++){
		lps[i].push_back({0 , i});
		for(int v : g[i]){
			for(pair<int , int> el : lps[v]){
				lps[i].push_back({el.first + 1 , el.second});
			}
			sort(lps[i].begin() , lps[i].end() , [](pair<int , int> a , pair<int , int>b){
				return (a.first > b.first);
			});
			
			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(pair<int , int> el : lps[r]){
				if(dels[el.second] != i + 1){
					res = el.first;
					break;
				}
			}
			cout << res << "\n";
		}
	}
}

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