Submission #1292185

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292185		blackscreen1	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1144 ms	113020 KiB

bitaro

#include <bits//stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_multiset;
#define ll long long
#define ld long double
#define iloop(m, h) for (auto i = m; i != h; i += (m < h ? 1 : -1))
#define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1))
#define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1))
#define lloop(m, h) for (auto l = m; l != h; l += (m < h ? 1 : -1))
#define iloop_(m, h, g) for (auto i = m; i < h; i += g)
#define jloop_(m, h, g) for (auto j = m; j < h; j += g)
#define kloop_(m, h, g) for (auto k = m; k < h; k += g)
#define lloop_(m, h, g) for (auto l = m; l < h; l += g)
#define getchar_unlocked _getchar_nolock // comment before submission
#define pll pair<ll, ll>
#define plll pair<ll, pll>
#define pllll pair<pll, pll>
#define vll vector<ll>
#define qll queue<ll>
#define dll deque<ll>
#define pqll priority_queue<ll>
#define gll greater<ll>
#define INF 1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
#define MOD3 1000000009
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
ll blk = 40;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n, m, q;
	cin >> n >> m >> q;
	vector<ll> adj[n+1];
	ll t1, t2;
	iloop(0, m) {
		cin >> t1 >> t2;
		adj[t2].push_back(t1);
	}
	priority_queue<pll> pq;
	ll vis[n+1];
	memset(vis, -1, sizeof(vis));
	vector<pll> rt[n+1];
	iloop(1, n+1) {
		pq.push({0, i});
		for (auto it : adj[i]) for (auto it2 : rt[it]) pq.push(make_pair(it2.first + 1, it2.second));
		while (pq.size() && rt[i].size() < blk) {
			pll nd = pq.top();
			pq.pop();
			if (vis[nd.second] == i) continue;
			vis[nd.second] = i;
			rt[i].push_back(nd);
		}
		pq = priority_queue<pll>();
	}
	ll t, x, b[n+1];
	memset(vis, -1, sizeof(vis));
	bool c;
	while (q--) {
		cin >> t >> x;
		iloop(0, x) {cin >> t1; vis[t1] = q;}
		if (x < blk) {
			c = 0;
			for (auto it : rt[t]) if (vis[it.second] != q) {cout << it.first; c = 1; break;}
			if (!c) cout << -1;
		}
		else {
			memset(b, 0, sizeof(b));
			iloop(1, t+1) {
				if (vis[i] == q) {b[i] = -INF;}
				for (auto it : adj[i]) b[i] = max(b[i], b[it] + 1);
			}
			cout << (b[t] >= 0 ? b[t] : -1);
		}
		cout << "\n";
	}
}

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