Submission #477942

#	Time	Username	Problem	Language	Result	Execution time	Memory
477942		amunduzbaev	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1716 ms	417872 KiB

bitaro

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

#define ar array
const int N = 2e5 + 5;
const int B = 350;
int n, m, q;
vector<int> edges[N];
vector<ar<int, 2>> par[N];

void build(){
	vector<int> used(n + 1), cost(n + 1);
	for(int i=1;i<=n;i++){
		vector<int> rr;
		cost[i] = 0, rr.push_back(i);
		for(auto x : edges[i]){
			for(auto v : par[x]){
				if(used[v[1]] == i){
					cost[v[1]] = max(cost[v[1]], v[0] + 1);
				} else {
					rr.push_back(v[1]);
					used[v[1]] = i;
					cost[v[1]] = v[0] + 1;
				}
			}
		}
		
		sort(rr.begin(), rr.end(), [&](int a, int b){
			return cost[a] > cost[b];
		});
		
		rr.resize(min((int)rr.size(), B));
		for(auto x : rr) par[i].push_back({cost[x], x});
	}
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0); 

	cin>>n>>m>>q;
	for(int i=0;i<m;i++){
		int a, b; cin>>a>>b;
		edges[b].push_back(a);
	}
	
	build();
	vector<int> used(n + 1);
	
	while(q--){
		int u; cin>>u;
		int sz, res = -1; cin>>sz;
		vector<int> a(sz);
		for(auto& x : a) cin>>x, used[x] = 1;
		
		if(sz >= B){
			vector<int> dis(n + 1, -1);
			for(int i=1;i<=n;i++){
				if(!used[i]) dis[i] = 0;
				for(auto x : edges[i]){
					if(~dis[x]) dis[i] = max(dis[i], dis[x] + 1);
				}
			} res = dis[u];
		} else {
			for(auto x : par[u]){
				if(used[x[1]]) continue;
				res = x[0];
				break;
			}
		}
		
		cout<<res<<"\n";
		for(auto x : a) used[x] = 0;
	}
}

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