Submission #1288661

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288661		c4l	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1175 ms	423368 KiB

bitaro

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
vector<int> a[100001], b[100001];
vector<pair<int, int>> luu[100001];
int mx[100001];
int s = 320;
int dp[100001];
vector<bool> tag(100001, false), vst(100001, false);
vector<int> topo;
void dfs(int u){
	vst[u] = true;
	for (int v:b[u]){
		if(!vst[v])dfs(v);
	}
	topo.push_back(u);
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m, q;
	cin >> n >> m >> q;
	for (int i = 1;i<=m;++i){
		int u, v;
		cin >> u >> v;
		a[u].push_back(v);
		b[v].push_back(u);
	}
	for (int u = 1;u<=n;++u){
		luu[u].push_back({0, u});
		for (int v:b[u]){
			for (auto i:luu[v]){
				if(mx[i.s]==0){
					luu[u].push_back(i);
					mx[i.s] = i.f+1;
				}else mx[i.s] = max(mx[i.s], i.f+1);
			}
		}
		sort(luu[u].begin(), luu[u].end(), [](pair<int, int> p, pair<int, int> q){
			return mx[p.s] > mx[q.s];
		});
		while(luu[u].size() > s){
			auto [d, v] = luu[u].back();
			mx[v] = 0;
			luu[u].pop_back();
		}
		for (auto &i:luu[u]){
			i.f = mx[i.s];
			mx[i.s] = 0;
		}
	}
	while(q--){
		int t, y;
		cin >> t >> y;
		vector<int> tmp;
		for (int i = 1;i<=y;++i){
			int tt;
			cin >> tt;
			tag[tt] = true;
			tmp.push_back(tt);
		}
		if(y<s){
			int res = -1;
			for (auto i:luu[t]){
				if(!tag[i.s]){
					res= i.f;
					break;
				}
			}
			for (int i:tmp){
				tag[i] = false;
			}
			cout << res << '\n';
		}else{
			int res = -1;
			for (int i =1;i<=n;++i){
				dp[i] = -1;
				vst[i] = false;
			}
			topo.clear();
			dfs(t);
			reverse(topo.begin(), topo.end());
			dp[t] = 0;
			for (int u:topo){
				for (int v:b[u]){
					dp[v] = max(dp[v], dp[u]+1);
				}
			}
			for (int i = 1;i<=n;++i){
				if(!tag[i])res = max(res, dp[i]);
			}
			for (int i:tmp){
				tag[i] = false;
			}
			cout << res << '\n';
		}
	}
}

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