Submission #236142

#	Time	Username	Problem	Language	Result	Execution time	Memory
236142		oolimry	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1532 ms	141052 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 = 100;

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

void dfs(int u){
	best[u].push_back(ii(0,u));
	
	for(int v : adj[u]){
		if(best[v].empty()) dfs(v);
		for(ii x : best[v]){
			int pos = inTemp[x.node];
			if(pos == 0){
				inTemp[x.node] = (int) best[u].size();
				best[u].push_back(ii(x.dist+1,x.node));
			}
			else{
				best[u][pos].dist = max(best[u][pos].dist,x.dist+1);
			}
		}
	}
	
	for(ii x : best[u]) inTemp[x.node] = 0;
	
	nth_element(best[u].begin(), best[u].begin() + B, best[u].end(), [&](ii a, ii b){ return a.dist > b.dist; });
	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;
	fill(inTemp, inTemp+n+1, -1);
	
	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 = max(ans,x.dist);
				}
			}
			cout << ans << "\n";
		}	
		
		for(int x : cannot) ban[x] = false;
	}
	
}

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