Submission #883733

#	Time	Username	Problem	Language	Result	Execution time	Memory
883733		Hakiers	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1755 ms	419816 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 1e5 + 7;
constexpr int SQRT = 300;
vector<int> G[MAXN];
vector<pair<int, int>> dp[MAXN];
int dist[MAXN];
bool visited[MAXN];
int ans[MAXN];
int n, m, q;

void compute(int v){
	vector<int> tmp;
	ans[v] = -1;
	dist[v] = 0;
	tmp.push_back(v);
	
	for(auto u : G[v]){
		for(auto [D, k] : dp[u]){	
			if(!dist[k])
				tmp.push_back(k);
			dist[k] = max(dist[k], D + 1);
		}
	}
	
	for(auto x : tmp){
		dp[v].push_back({dist[x], x});
		dist[x] = 0;
	}
	
	sort(dp[v].begin(), dp[v].end());
	reverse(dp[v].begin(), dp[v].end());
	
	while(dp[v].size() > SQRT)
		dp[v].pop_back();

}

void dfs(int v){
	if(dist[v] != -1)
		dist[v] = 0;
	visited[v] = 1;
	
	for(auto u : G[v]){
		if(!visited[u]) dfs(u);
		
		if(dist[u] == -1) continue;
		dist[v] = max(dist[v], dist[u] + 1);
	}
}

int ans1(int v, int l){
	
	for(int i = 1; i <= l; i++){
		int u;
		cin >> u;
		dist[u] = -1;
	}
		
	dfs(v);
	int res = dist[v];
	
	for(int i = 1; i <= n; i++)
		visited[i] = dist[i] = 0;
	
	return res;
}

int ans2(int v, int l){
	for(auto [x, u] : dp[v])
		ans[u] = x;
	
		
	for(int i = 1; i <= l; i++){
		int u;
		cin >> u;
		ans[u] = -1;
	}
	
	
	int res = -1;
	for(auto [x, u] : dp[v]){
		res = max(res, ans[u]);
		ans[u] = -1;
	}
	
	return res;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> q;
	
	for(int i = 1; i <= m; i++){
		int u, v;
		cin >> u >> v;
		G[v].push_back(u);
	}
	
	for(int i = 1; i <= n; i++)
		compute(i);
	
	
	for(int i = 1; i <= q; i++){
		int v, l;
		cin >> v >> l;
		if(l >= SQRT) cout << ans1(v, l) << "\n";
		else cout << ans2(v, l) << "\n";
	}
}

Compilation message (stderr)

bitaro.cpp: In function 'int ans1(int, int)':
bitaro.cpp:64:24: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   64 |   visited[i] = dist[i] = 0;
      |                ~~~~~~~~^~~

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