Submission #391163

#	Time	Username	Problem	Language	Result	Execution time	Memory
391163		sinamhdv	Bitaro’s Party (JOI18_bitaro)	C++11	100 / 100	1999 ms	116572 KiB

bitaro

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define endl '\n'

#define MAXN 100100
#define SQ 100

int n, m, q;
vector<int> adj[MAXN], badj[MAXN];
int fw[MAXN];
bool busy[MAXN];
bool added[MAXN];
vector<pii> dp[MAXN];

void merge(vector<pii> dp, vector<pii> &stk)
{
	vector<int> advec;
	vector<pii> vec;
	while ((int)vec.size() < SQ)
	{
		pii p = dp.back();
		p.fr++;
		
		if (p > stk.back()) dp.pop_back();
		else p = stk.back(), stk.pop_back();

		if (added[p.sc]) continue;
		if (p.fr < 0) break;
		added[p.sc] = true;
		advec.pb(p.sc);
		vec.pb(p);
	}
	while ((int)vec.size() < SQ + 1)
		vec.pb({-INF, 0});
	reverse(all(vec));
	stk.swap(vec);
	for (int u : advec) added[u] = false;
}

int32_t main(void)
{
	fast_io;
	cin >> n >> m >> q;
	FOR(i, 0, m)
	{
		int x, y;
		cin >> x >> y;
		adj[x].pb(y);
		badj[y].pb(x);
	}

	FOR(v, 1, n + 1)
	{
		vector<pii> stk;
		FOR(j, 0, SQ) stk.pb({-INF, 0});
		stk.pb({0, v});

		for (int u : badj[v])
			merge(dp[u], stk);

		dp[v].swap(stk);
	}

	while (q--)
	{
		int t, y;
		vector<int> bs;
		cin >> t >> y;
		FOR(i, 0, y)
		{
			int x;
			cin >> x;
			busy[x] = true;
			bs.pb(x);
		}
		if (y >= SQ)
		{
			int ans = -INF;
			fill(fw, fw + n + 10, -INF);
			fw[t] = 0;
			for (int i = n; i >= 1; i--)
			{
				for (int u : adj[i])
					fw[i] = max(fw[i], fw[u] + 1);
				if (!busy[i])
					ans = max(ans, fw[i]);
			}
			if (ans < 0) cout << "-1\n";
			else cout << ans << endl;
		}
		else
		{
			for (int i = SQ; i >= 0; i--)
				if (!busy[dp[t][i].sc])
				{
					int ans = dp[t][i].fr;
					if (ans < 0) cout << "-1\n";
					else cout << ans << endl;
					break;
				}
		}
		for (int u : bs)
			busy[u] = false;
	}
	return 0;
}

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