Submission #1322116

#	Time	Username	Problem	Language	Result	Execution time	Memory
1322116		lwham	Bitaro’s Party (JOI18_bitaro)	C++20	7 / 100	2094 ms	18376 KiB

bitaro

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int maxn = 1e5;
const int sq = 336;

vector<int> adj[maxn],in[maxn];
set<pair<int,int>> st[maxn];
int u,v,q,n,m,y,c,h,currt[maxn],res;

void inp(){
	cin >> n >> m >> q;
	for (int i = 1 ; i <= m; i++){
		cin >> u >> v;
		adj[u].push_back(v);
		in[v].push_back(u);
	}
	fill(currt, currt+n+1, -1);
}
void prep(){
	for (int i = 1 ; i <= n ; i++){
		st[i].insert({0, i});
	}
	for (int i = 1 ; i <= n ; i++){
		set<pair<int,int>> bag;
		for (auto it : in[i]){
			for (auto el : st[it]){
				bag.insert(el);
			}
		}
		vector<bool> is(n+1, false);
		while ((int)bag.size() && (int)st[i].size() < sq){
			pair<int,int> p = *bag.rbegin();
			bag.erase(*bag.rbegin());
			if (is[p.second]) continue;
			is[p.second] = true;
			st[i].insert({p.first + 1, p.second});
		}
	}
}
void query(){
	if (q == 1){
		cin >> h >> y;
		for (int i = 1 ; i <= y ; i++){
			cin >> c;
			currt[c] = q;
		}
		vector<int> dp(n+1, -1);
		res = -1;
		dp[h] = 0;
		for (int i = n ; i >= 1 ; i--){
			for (auto it : adj[i]){
					if (dp[it] == -1) continue;
					dp[i] = max(dp[it] + 1, dp[i]);
				}
				if (currt[i] != q) res = max(res, dp[i]);
		}
		cout << res << '\n';
	}
	else{
		while (q--){
			cin >> h >> y;
			for (int i = 1 ; i <= y ; i++){
				cin >> c;
				currt[c] = q;
			}
			if (y < sq){
				res = -1;
				for (auto it : st[h]){
					if (currt[it.second] != q){
						res = max(res, it.first);
					}
				}
				if (currt[h] != q) res = max(res, 0);
			}
			else{ // dp
				vector<int> dp(n+1, -1);
				res = -1;
				dp[h] = 0;
				for (int i = n ; i >= 1 ; i--){
					for (auto it : adj[i]){
						if (dp[it] == -1) continue;
						dp[i] = max(dp[it] + 1, dp[i]);
					}
					if (currt[i] != q) res = max(res, dp[i]);
				}
			}
			cout << res << '\n';
		}
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	inp();
	prep();
	query();
}

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