Submission #369772

#	Time	Username	Problem	Language	Result	Execution time	Memory
369772		8e7	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1610 ms	267628 KiB

bitaro

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
const int siz = 320;
vector<int> adj[maxn], from[maxn];
pii pnt[maxn][siz + 3];
pii tmp[siz + 3];
int num[maxn];
 
inline bool cmp (pii a, pii b) {
	return a.ss > b.ss;
}
 
 
int dp[maxn];
bool part[maxn], found[maxn];
void getdp(int n, int id) {
	for (int i = 1;i <= id;i++) dp[i] = 0;
	for (int i = 1;i <= id;i++) {
		for (int v:adj[i]) {
			dp[v] = max(dp[v], (dp[i] == 0 ? (part[i] ? -1 : 0) : dp[i]) + 1);
		}
	}
}
void merge(int a, int b) {
	int n = num[a], m = num[b], ind = 0, c = 0;
	for (int i = 0;i < n;i++) {
		while (ind < m && pnt[b][ind].ss + 1 > pnt[a][i].ss) {
			if (!found[pnt[b][ind].ff]) {
				found[pnt[b][ind].ff] = 1;
				tmp[c++] = make_pair(pnt[b][ind].ff, pnt[b][ind].ss + 1);
			}
			ind++;
			if (c > siz) break;
		}
		if (!found[pnt[a][i].ff]) {
			found[pnt[a][i].ff] = 1;
			tmp[c++] = pnt[a][i];
		}
		if (c > siz) break;
	}
	while (ind < m) {
		if (!found[pnt[b][ind].ff]) {
			found[pnt[b][ind].ff] = 1;
			tmp[c++] = make_pair(pnt[b][ind].ff, pnt[b][ind].ss + 1);
		}
		ind++;
		if (c > siz) break;
	}
	for (int i = 0;i < c;i++) found[tmp[i].ff] = 0;
	num[a] = min(siz, c);
	for (int i = 0;i < num[a];i++) pnt[a][i] = tmp[i];
}
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n, m, q;
	cin >> n >> m >> q;
	for (int i = 0;i < m;i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		from[b].push_back(a);
	}
	for (int i = 1;i <= n;i++) {
		num[i] = 1;
		pnt[i][0] = make_pair(i, 0);
		for (int v:from[i]) {
			merge(i, v);
		}
	}
	getdp(n, n);
	while (q--) {
		int ind, yi;
		cin >> ind >> yi;
		vector<int> val;
		for (int i = 0;i < yi;i++) {
			int x;
			cin >> x;
			if (x <= ind) part[x] = 1, val.push_back(x);
		}
		if (yi >= siz) {
			getdp(n, ind);
			if (part[ind] && dp[ind] == 0) cout << -1 << "\n";
			else cout << dp[ind] << "\n";
		} else {
			int ans = -1;
			for (int v = 0;v < num[ind];v++) {
				if (!part[pnt[ind][v].ff]) ans = max(ans, pnt[ind][v].ss);
			}
			cout << ans << "\n";
		}
		for (int i:val) part[i] = 0;
	}
}
/*
5 6 3
1 2
2 4
3 4
1 3
3 5
4 5
4 1 1
5 2 2 3
2 3 1 4 5
 */

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