제출 #377574

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

bitaro

#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 1e5 + 7;

vi G[N]; // from
V<pi> who[N];
int n, m, q, k;
bitset<N> s, no;

signed main()
{
	IO_OP;

	cin >> n >> m >> q;
	k = sqrt(n);
	for(int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		G[v].PB(u);		
	}
	for(int u = 1; u <= n; u++) {
		who[u].EB(0, u);
		for(int v:G[u]) {
			V<pi> tt = who[v], ttt;
			swap(ttt, who[u]);
			for(pi& i:tt) i.F--;
			who[u].resize(tt.size() + ttt.size());
			int top = 0;
			for(int i = 0, j = 0; top < k && (i < int(tt.size()) || j < int(ttt.size()));) {
				auto add = [&] (pi& p) {
					if(s[p.S] == 0) {
						s[p.S] = 1;
						who[u][top++] = p;
					}
				};
				if(j == int(ttt.size()) || (i < int(tt.size()) && tt[i].F < ttt[j].F)) {
					add(tt[i++]);
				} else {
					add(ttt[j++]);
				}
			}
			who[u].resize(top);
			for(pi& p:who[u]) s[p.S] = 0;
		}
	}
	while(q--) {
		int u, y;
		cin >> u >> y;
		vi x(y);
		for(int i = 0; i < y; i++) {
			cin >> x[i];
			no[x[i]] = 1;
		}
		if(y >= k) {
			vi vis(n + 1), dp(n + 1);
			function<int(int)> DP = [&] (int u) {
				if(vis[u]) return dp[u];
				vis[u] = 1;
				if(no[u]) dp[u] = -INF;
				else dp[u] = 0;
 				for(int v:G[u]) {
					dp[u] = max(dp[u], DP(v) + 1);
				}
				return dp[u];
			};
			cout << max(DP(u), -1) << '\n';
		} else {
			int ans = -1;
			for(pi p:who[u]) {
				if(no[p.S] == 0) {
					ans = -p.F;
					break;
				}
			}
			cout << ans << '\n';
		}
		for(int i = 0; i < y; i++) no[x[i]] = 0;
	}

}

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