Submission #530391

#	Time	Username	Problem	Language	Result	Execution time	Memory
530391		akhan42	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	2060 ms	417632 KiB

bitaro

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
//using namespace __gnu_pbds;

#define F first
#define S second
#define forn(i, n) for(int i = 0; i < n; ++i)
#define forbn(i, b, n) for(int i = b; i < n; ++i)
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define min3(a, b, c) min(a, min(b, c))
#define at(m, k) (m.find(k) != m.end() ? m[k]: 0)

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long ll;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

template <class T> inline void mineq(T &a, T b) { a = min(a, b); }
template <class T> inline void maxeq(T &a, T b) { a = max(a, b); }


const int MX = 100 * 1000 + 10;
int sq = 300;
vi gr[MX];
vii farthest[MX];
bool busy[MX];
bool att[MX];
vi d1;


int dfs1(int node) {
	if(d1[node] != -1) return d1[node];

	int mx = 0;
	for(int nb: gr[node]) {
		if(busy[nb]) {
			int val = dfs1(nb);
			if(val)
				maxeq(mx, val + 1);
		}
		else
			maxeq(mx, dfs1(nb) + 1);
	}

	d1[node] = mx;
	return mx;
}


void dfs2(int node) {
	if(att[node]) return;
	att[node] = true;

	vii ans;
	ans.eb(0, node);

	for(int nb: gr[node]) {
		dfs2(nb);

		for(ii p: farthest[nb])
			ans.eb(p.F + 1, p.S);
	}

	sort(all(ans), greater<ii>());
	for(int i = 0; i < sq && i < sz(ans); i++)
		farthest[node].pb(ans[i]);
}


void solve() {
	int n, m, q;
	cin >> n >> m >> q;
	forn(_, m) {
		int a, b;
		cin >> a >> b;
		gr[b].pb(a);
	}

	forbn(node, 1, n + 1)
		dfs2(node);

	forn(_, q) {
		int t, Y;
		cin >> t >> Y;
		vi ys(Y);

		forn(j, Y) {
			cin >> ys[j];
			busy[ys[j]] = true;
		}

		if(Y >= sq || true) {
			d1.assign(n + 1, -1);
			int val = dfs1(t);
			if(val == 0 && busy[t])
				cout << -1 << '\n';
			else
				cout << val << '\n';
		} else {
			bool printed = false;
			for(ii node: farthest[t]) {
				if(!busy[node.S]) {
					cout << node.F << '\n';
					printed = true;
					break;
				}
			}
			if(!printed)
				cout << -1 << '\n';
		}

		for(int y: ys)
			busy[y] = false;
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

//	freopen("haybales.in", "r", stdin);
//	freopen("haybales.out", "w", stdout);

	int t = 1;
//	cin >> t;
	while(t--) {
		solve();
	}
}

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