Submission #839268

#	Time	Username	Problem	Language	Result	Execution time	Memory
839268		serifefedartar	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1096 ms	255392 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
 
#define debug(x) {cout << #x << ": "; for (auto it : x) cout << it << " ";cout << endl;}
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 1000000007
#define LOGN 15
#define MAXN 100005

const int SQRT = 300;
vector<vector<int>> graph, rev;
vector<vector<pair<int,int>>> dist;
bool closed[MAXN], taken[MAXN];
void get(int to, int from) {
	int sz_to = dist[to].size();
	int sz_from = dist[from].size();
	int t_i = sz_to - 1, f_i = sz_from - 1;
	vector<pair<int,int>> new_l;
	while (new_l.size() < SQRT && (f_i >= 0 || t_i >= 0)) {
		pair<int,int> now = {-1, -1};
		if (f_i >= 0 && dist[from][f_i].s + 1 >= now.s)
			now = {dist[from][f_i].f, dist[from][f_i].s + 1};
		if (t_i >= 0 && dist[to][t_i].s >= now.s)
			now = dist[to][t_i];
		if (!taken[now.f]) {
			new_l.push_back(now);
			taken[now.f] = true; 
		}

		while (t_i >= 0 && dist[to][t_i].f == now.f)
			t_i--;
		while (f_i >= 0 && dist[from][f_i].f == now.f)
			f_i--;
	}
	reverse(new_l.begin(), new_l.end());
	dist[to] = new_l;
	for (auto u : new_l)
		taken[u.f] = false;
}

int main() {
	fast
	int N, M, Q, S, E;
	cin >> N >> M >> Q;

	graph = vector<vector<int>>(N+1, vector<int>());
	rev = vector<vector<int>>(N+1, vector<int>());
	dist = vector<vector<pair<int,int>>>(N+1, vector<pair<int,int>>());
	for (int i = 0; i < M; i++) {
		cin >> S >> E;
		graph[S].push_back(E); 
		rev[E].push_back(S); 
	}

	for (int i = 1; i <= N; i++)
		dist[i].push_back({i, 0});

	for (int i = 1; i <= N; i++) {
		for (auto u : graph[i])
			get(u, i);
	}

	while (Q--) {
		int town, cnt;
		cin >> town >> cnt;
		vector<int> towns(cnt);
		for (int i = 0; i < cnt; i++) {
			cin >> towns[i];
			closed[towns[i]] = true;
		}

		int ans = -1;
		if (cnt >= SQRT) {
			vector<int> new_dist(N+1, -1e8); 
			new_dist[town] = 0;
			for (int i = town; i >= 1; i--) {
				if (new_dist[i] < 0)
					continue ;
				for (auto u : rev[i])
					new_dist[u] = max(new_dist[u], new_dist[i] + 1);
			}

			for (int i = 1; i <= town; i++) {
				if (!closed[i])
					ans = max(ans, new_dist[i]); 
			}
		} else {
			for (auto u : dist[town]) {
				if (!closed[u.f])
					ans = max(ans, u.s);
			}
		}
		cout << ans << "\n"; 

		for (auto u : towns)
			closed[u] = false; 
	}
}

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