제출 #59439

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59439		tmwilliamlin168	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	1678 ms	113536 KiB

bitaro

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

#define pii pair<int, int>
#define fi first
#define se second

const int mxN=1e5, bs=80;
int n, m, q, dp2[mxN], c[mxN];
vector<int> adj[mxN];
vector<pii> dp1[mxN];
bool a[mxN];

void cdp1(int u) {
	if(!dp1[u].empty())
		return;
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	pq.push({0, u});
	for(int v : adj[u]) {
		cdp1(v);
		for(pii p : dp1[v]) {
			pq.push({p.fi+1, p.se});
			if(pq.size()>bs)
				pq.pop();
		}
	}
	while(!pq.empty()) {
		dp1[u].push_back(pq.top());
		pq.pop();
	}
}

int cdp2(int u) {
	if(dp2[u]==-1) {
		dp2[u]=a[u]?-n:0;
		for(int v : adj[u])
			dp2[u]=max(cdp2(v)+1, dp2[u]);
	}
	return dp2[u];
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m >> q;
	while(m--) {
		int u, v;
		cin >> u >> v, --u, --v;
		adj[v].push_back(u);
	}
	for(int i=0; i<n; ++i)
		cdp1(i);
	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) {
			memset(dp2, -1, 4*n);
			cdp2(t);
			ans=max(dp2[t], ans);
		} else {
			for(int i=dp1[t].size()-1; i>=0; --i) {
				if(a[dp1[t][i].se])
					continue;
				ans=dp1[t][i].fi;
				break;
			}
		}
		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