Submission #389894

#	Time	Username	Problem	Language	Result	Execution time	Memory
389894		sinamhdv	Bitaro’s Party (JOI18_bitaro)	C++11	14 / 100	2040 ms	93336 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];
pii dp[MAXN][SQ];
int fw[MAXN];
bool busy[MAXN];
bool added[MAXN];

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(i, 0, MAXN) FOR(j, 0, SQ) dp[i][j].fr = -INF;
	FOR(v, 1, n + 1)
	{
		vector<pii> vec;
		vector<int> advec;

		for (int u : badj[v])
			FOR(i, 0, SQ) vec.pb({dp[u][i].fr + 1, dp[u][i].sc});
		vec.pb({0, v});
		sort(all(vec), greater<pii>());
		int ptr = 0;
		for (pii p : vec)
		{
			if (added[p.sc]) continue;
			dp[v][ptr++] = p;
			added[p.sc] = true;
			advec.pb(p.sc);
			if (ptr >= SQ) break;
		}
		for (; ptr < SQ; ptr++)
			dp[v][ptr] = {-INF, 0};
		for (int u : advec)
			added[u] = false;
	}

	while (q--)
	{
		int t, y;
		cin >> t >> y;
		vector<int> bs;
		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(i, 0, SQ)
				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: 0 / 86