제출 #1053845

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1053845		Minbaev	Bitaro’s Party (JOI18_bitaro)	C++17	0 / 100	9 ms	13148 KiB

bitaro

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
const int N = 2e5 + 5;
const int B = 320;
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;
			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: 0 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 86