Submission #1322113

#TimeUsernameProblemLanguageResultExecution timeMemory
1322113lwhamBitaro’s Party (JOI18_bitaro)C++20
7 / 100
2095 ms18364 KiB
#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(){
	while (q--){
		cin >> h >> y;
		for (int i = 1 ; i <= y ; i++){
			cin >> c;
			currt[c] = q;
		}
		if (q != 1 && 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();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...