Submission #377587

#	Time	Username	Problem	Language	Result	Execution time	Memory
377587		cheissmart	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1194 ms	262764 KiB

bitaro

#include <iostream>
#include <algorithm>
#include <vector>
#include <bitset>
#include <functional>
#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 = 320;
	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];
			V<pi> ttt;
			swap(ttt, who[u]);
			who[u].resize(k);
			int top = 0;
			for(int i = 0, j = 0; 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 - 1 < ttt[j].F)) {
					add(MP(tt[i].F - 1, tt[i].S));
					i++;
				} else {
					add(ttt[j++]);
				}
				if(!(top ^ k)) break;
			}
			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 dp(u + 1);
			for(int i = 1; i <= u; i++) {
				if(no[i]) dp[i] = -INF;
				else dp[i] = 0;
 				for(int j:G[i]) dp[i] = max(dp[i], dp[j] + 1);
			}
			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: 86 / 86