Submission #1255713

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255713		namhh	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	5 ms	5448 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int N = 1e5+5;
const int block = 317;
int n,m,q,cur[N],vis[N],dp[N],busy[N],ck[N];
vector<int>adj[N];
vector<pii>aqua[N];
void dijkstra(){
	for(int i = 1; i <= n; i++){
		priority_queue<pii>pq;
		for(int j: adj[i]) pq.push({aqua[j][0].fi,j});
		while(!pq.empty() && aqua[i].size() < block){
			auto[c,u] = pq.top();
			pq.pop();
			int v = aqua[u][cur[u]].se;
			if(!vis[v]){
				vis[v] = 1;
				aqua[i].push_back({c+1,v});
			}
			cur[u]++;
			if(cur[u] < aqua[u].size()) pq.push({aqua[u][cur[u]].fi,u});
		}
		if(aqua[i].size() < block) aqua[i].push_back({0,i});
		for(auto v: aqua[i]) vis[v.se] = 0;
		for(int v: adj[i]) cur[v] = 0;
	}
}
int main(){
	cin >> n >> m >> q;
	for(int i = 1; i <= m; i++){
		int u,v;
		cin >> u >> v;
		adj[v].push_back(u);
	}
	dijkstra();
	while(q--){
		int t,y;
		cin >> t >> y;
		for(int i = 1; i <= y; i++){
			cin >> ck[i];
			busy[ck[i]] = 1;
		}
		if(y >= block){
			for(int i = 1; i <= t; i++) dp[i] = 0;
			for(int i = 1; i <= t; i++){
				for(int v: adj[i]){
					if(!busy[v]) dp[i] = max(dp[i],dp[v]+1);
				}
			}
			cout << (dp[t] == 0) ? -1 : dp[t];
			cout << "\n";
		}
		else{
			bool ck = true;
			for(auto v: aqua[t]){
				if(!busy[v.se]){
					cout << v.fi << "\n";
					ck = false;
					break;
				}
			}
			if(ck == true) cout << -1 << "\n";
		}
		for(int i = 1; i <= y; i++) busy[ck[i]] = 0;
	}
}

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