Submission #1123661

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123661		ZeroCool	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	8 ms	11332 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define ar array
#define ld long double
#define all(v) v.begin(),v.end()
const int INF = 1e18 + 10;
const int N = 2e5 + 20;
const int SQRT = 400;

int n, m, q;
int dp[N];

vector<int> g[N];

void calc(int x){
	memset(dp, -0x3f, sizeof dp);
	dp[x] = 0;
	for(int i = x;i >= 0;i--){
		for(auto u: g[i])dp[u] = max(dp[u], dp[i] + 1);
	}
}

vector<ar<int, 2>> lps[N];

vector<ar<int, 2>> join(vector<ar<int, 2>> a, vector<ar<int, 2>> b){
	vector<ar<int, 2>> v;
	reverse(all(a));
	reverse(all(b));
	merge(all(a), all(b), back_inserter(v));
	reverse(all(v));
	while(v.size() > SQRT)v.pop_back();
	return v;
}

void kurac(){
	for(int i = 0;i < n;i++){
		for(auto u: g[i])lps[i] = join(lps[i], lps[u]);
		for(auto &[a, b]: lps[i])++a;
		lps[i] = join(lps[i], {{0, i}});
	}
}

int del[N];

signed main(){ios_base::sync_with_stdio(false);cin.tie(0);
	cin>>n>>m>>q;
	while(m--){
		int a, b;
		cin>>a>>b;
		--a, --b;
		g[b].push_back(a);
	}
	memset(del, -1, sizeof del);
	kurac();
	while(q--){
		int x, y;
		cin>>x>>y;
		--x;
		while(y--){
			int t;
			cin>>t;
			--t;
			del[t] = q;
		}
		if(y > SQRT){
			calc(x);
			int ans = -1;
			for(int i = 0;i < n;i++){
				if(del[i] != q){
					ans = max(ans, dp[i]);
				}
			}
			cout<<ans<<'\n';
		}else{
			for(auto [a, b]: lps[x]){
				if(del[b] != q){
					cout<<a<<'\n';
					break;
				}
			}
		}
		
	}
}

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