제출 #236121

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
236121		oolimry	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	2101 ms	30328 KiB

bitaro

#include <bits/stdc++.h>
#define node second
#define dist first
#define all(x) x.begin(), x.end()
using namespace std;
typedef pair<int,int> ii;

const int B = 10;

vector<ii> best[100005];
vector<int> adj[100005];
bool ban[100005];
int memo[100005];
int vis[100005];

void dfs(int u){
	vector<ii> temp;
	
	for(int v : adj[u]){
		if(best[v].empty()) dfs(v);
		for(ii x : best[v]) temp.push_back(x);
	}	
	
	sort(all(temp), [&](ii a, ii b){
		if(a.node == b.node) return a.dist < b.dist;
		return a.node < b.node;
	});
	
	for(int i = 0;i < (int) temp.size();i++){
		if(i == (int)(temp.size()-1) || temp[i].node != temp[i+1].node){
			best[u].push_back(ii(temp[i].dist+1, temp[i].node));
		}
	}
	
	best[u].push_back(ii(0,u));
	sort(all(best[u]), greater<ii>());
	
	while(best[u].size() > B) best[u].pop_back();
	vis[u] = true;
}

int dfs2(int u){
	if(memo[u] != -1) return memo[u];
	
	int ans = 0;
	if(ban[u]) ans = -10234567;
	
	for(int v : adj[u]){
		ans = max(ans, dfs2(v)+1);
	}
	
	memo[u] = ans;
	
	return memo[u];
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	int n, m, Q; cin >> n >> m >> Q;
	
	while(m--){
		int u, v; cin >> u >> v;
		adj[v].push_back(u);
	}
	
	for(int i = 1;i <= n;i++){
		if(!vis[i]) dfs(i);
	}
		
	while(Q--){
		
		int t; cin >> t;
		int S; cin >> S;
		
		vector<int> cannot;
		
		for(int i = 0;i < S;i++){
			int x; cin >> x;
			cannot.push_back(x);
		}
		for(int x : cannot) ban[x] = true;
		
		if(S >= B){
			fill(memo, memo+n+1, -1);
			
			cout << max(-1, dfs2(t)) << "\n";
		}
		else{
			int ans = -1;
			for(ii x : best[t]){
				if(!ban[x.node]){
					ans = x.dist;
					break;
				}
			}
			cout << ans << "\n";
		}	
		
		for(int x : cannot) ban[x] = false;
	}
	
}

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