제출 #305621

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
305621		youngyojun	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1649 ms	279632 KiB

bitaro

#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef pair<int, int> pii;
 
const int MAXN = 100005;
const int MAXM = 200005;
const int MAXQ = 100005;
const int SQRN = 335;
 
vector<int> G[MAXN];
 
pii V[MAXN][SQRN]; int Vn[MAXN];
 
int dp[MAXN];
int chk[MAXN], chkn;
 
vector<int> DV[MAXQ];
int C[MAXQ], D[MAXQ];
int A[MAXM], B[MAXM];
 
int N, M, Q;
 
int main() {
	ios::sync_with_stdio(false);
 
	cin >> N >> M >> Q;
	for(int i = 1; i <= M; i++) cin >> A[i] >> B[i];
	for(int i = 1; i <= Q; i++) {
		cin >> C[i] >> D[i];
		for(int j = 0, v; j < D[i]; j++) {
			cin >> v;
			DV[i].eb(v);
		}
	}
 
	for(int i = 1; i <= M; i++) G[B[i]].eb(A[i]);
 
	for(int i = 1; i <= N; i++) {
		pii *V = ::V[i];
		int &Vn = ::Vn[i];
		chkn++;
 
		priority_queue<pair<int, pii>> PQ;
		for(int v : G[i]) PQ.push(pair<int, pii>(::V[v][0].second, pii(v, 0)));
 
		for(int v, idx, p; !PQ.empty() && Vn < SQRN;) {
			tie(v, idx) = PQ.top().second; PQ.pop();
			p = ::V[v][idx].first;
			if(chk[p] != chkn) {
				chk[p] = chkn;
				V[Vn] = ::V[v][idx]; Vn++;
			}
 
			for(idx++; idx < ::Vn[v] && chk[::V[v][idx].first] == chkn; idx++);
			if(::Vn[v] == idx) continue;
			PQ.push(pair<int, pii>(::V[v][idx].second, pii(v, idx)));
		}
		for(int j = 0; j < Vn; j++) V[j].second++;
		if(Vn < SQRN) V[Vn++] = pii(i, 0);
	}
 
	for(int qi = 1; qi <= Q; qi++) {
		chkn++; for(int v : DV[qi]) chk[v] = chkn;
 
		if(D[qi] < SQRN) {
			int ret = -1, idx = C[qi];
 
			for(int i = 0; i < Vn[idx]; i++) {
				if(chk[V[idx][i].first] != chkn) {
					ret = V[idx][i].second;
					break;
				}
			}
			printf("%d\n", ret);
		} else {
			fill(dp, dp+N+1, 0);
			dp[C[qi]] = 1;
 
			int ret = -1;
			for(int i = C[qi]; i; i--) {
				if(!dp[i]) continue;
				if(chk[i] != chkn) upmax(ret, dp[i] - 1);
				for(int v : G[i])
					upmax(dp[v], dp[i] + 1);
			}
			printf("%d\n", ret);
		}
	}
	return 0;
}

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