제출 #839257

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
839257		serifefedartar	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	2053 ms	215904 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 = 400;
vector<vector<int>> graph, rev;
vector<vector<pair<int,int>>> dist;
bool closed[MAXN];
void get(int to, int from) {
	vector<pair<int,int>> new_l;
	int l = 0;
	int sz = dist[to].size();
	for (auto u : dist[from]) {
		while (l < sz && dist[to][l].f < u.f) {
			new_l.push_back(dist[to][l]);
			l++;
		}

		new_l.push_back({u.f, u.s+1});
		if (l < sz && dist[to][l].f == new_l.back().f && dist[to][l].s > new_l.back().s) {
			new_l.pop_back();
			new_l.push_back({u.f, dist[to][l].s}); 
			l++;
		}
		if (l < sz && dist[to][l].f == new_l.back().f)
			l++;
	}
	sort(new_l.begin(), new_l.end(), [&](pair<int,int> &a, pair<int,int> &b) {
		return a.s > b.s;
	});

	while (new_l.size() > SQRT)
		new_l.pop_back();
	sort(new_l.begin(), new_l.end());

	dist[to] = new_l;
}

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 (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: 0 / 7
• Subtask 3: 0 / 86