Submission #100589

#	Time	Username	Problem	Language	Result	Execution time	Memory
100589		tmwilliamlin168	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	2058 ms	38364 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
 
#define ar array
 
const int mxN=1e5, bs=25;
int n, m, q, dp2[mxN], c[mxN];
vector<int> adj[mxN];
vector<ar<int, 2>> dp1[mxN];
priority_queue<ar<int, 2>, vector<ar<int, 2>>, greater<ar<int, 2>>> pq;
bool a[mxN];
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m >> q;
	for(int i=0, u, v; i<m; ++i)
		cin >> u >> v, --u, --v, adj[v].push_back(u);
	for(int i=0; i<n; ++i) {
		pq.push({0, i});
		int nd=c[i]=1;
		for(int v : adj[i]) {
			for(ar<int, 2> p : dp1[v]) {
				pq.push({p[0]+1, p[1]});
				nd+=!c[p[1]]++;
				while(nd>bs) {
					if(!--c[pq.top()[1]])
						--nd;
					pq.pop();
				}
			}
		}
		while(!pq.empty()) {
			if(!--c[pq.top()[1]])
				dp1[i].push_back(pq.top());
			pq.pop();
		}
	}
	while(q--) {
		int t, y, ans=-1;
		cin >> t >> y, --t;
		for(int i=0; i<y; ++i) {
			cin >> c[i], --c[i];
			a[c[i]]=1;
		}
		if(y>=bs) {
			for(int i=0; i<=t; ++i) {
				dp2[i]=a[i]?-n:0;
				for(int v : adj[i])
					dp2[i]=max(dp2[v]+1, dp2[i]);
			}
			ans=max(dp2[t], ans);
		} else 
			for(ar<int, 2> p : dp1[t])
				if(!a[p[1]])
					ans=p[0];
		for(int i=0; i<y; ++i)
			a[c[i]]=0;
		cout << ans << "\n";
	}
}

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