Submission #1234287

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234287		hashdfdfh	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1176 ms	217220 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1e5 + 5;
const int BASE = 150;

// 保存原始边信息
vector<int> edges[MAX_N];

// 保存颠倒后边信息
vector<int> edges2[MAX_N];

vector<pair<int, int>> nr[MAX_N];
int ok[MAX_N], dist[MAX_N], tag[MAX_N];

int n, m, q;

void process() {
	int start, y;
	cin >> start >> y;

	// 如果禁用比较多
	if (y >= BASE) {
		// 
		for (int j = 1; j <= n; j++) {
			ok[j] = 1;
			dist[j] = -1;
		}
		for (int j = 0; j < y; j++) {
			int x;
			cin >> x;
			ok[x] = 0;
		}
		for (int u = 1; u <= n; u++) {
			if (ok[u]) {
				dist[u] = max(dist[u], 0);
			}
			if (dist[u] >= 0) {
				for (auto v : edges[u]) {
					dist[v] = max(dist[v], dist[u] + 1);
				}
			}
		}
		cout << dist[start] << endl;
	}
	// 如果禁用比较少
	else {
		vector<int> nd;
		while (y--) {
			int x;
			cin >> x;
			tag[x] = 1;
		}
		
		int maxv = -1;
		for (auto v : nr[start]) {
			if (!tag[v.second]) {
				maxv = v.first;
				break;
			}
		}
		memset(tag, 0, sizeof(tag));
		cout << maxv << endl;
	}
}

signed main() {
	cin >> n >> m >> q;

	// 读取边信息
	for (int i = 1; i <= m; i++) {
		int u, v; 
		cin >> u >> v;

		// 保存原始图
		edges[u].push_back(v);

		// 保存颠倒以后图
		edges2[v].push_back(u);
	}

	for (int i = 1; i <= n; i++) {
		if (nr[i].size() < BASE) {
			nr[i].push_back(make_pair(0, i));
		}
		for (auto v : edges[i]) {
			vector<pair<int, int>> nw;
			int it1 = 0, it2 = 0;
			while (((it1 != nr[i].size()) || (it2 != nr[v].size())) && (nw.size() < BASE)) {
				if (it1 == nr[i].size()) {
					if (tag[nr[v][it2].second]) {
						it2++;
						continue;
					}  tag[nr[v][it2].second] = 1;
					nw.push_back(nr[v][it2]);
					it2++;
					continue;
				}
				if (it2 == nr[v].size()) {
					if (tag[nr[i][it1].second]) {
						it1++;
						continue;
					} tag[nr[i][it1].second] = 1;
					auto t = nr[i][it1];
					t.first++;
					nw.push_back(t);
					it1++;
					continue;
				}
				if (nr[i][it1].first + 1 > nr[v][it2].first) {
					if (tag[nr[i][it1].second]) {
						it1++;
						continue;
					} tag[nr[i][it1].second] = 1;
					auto t = nr[i][it1];
					t.first++;
					nw.push_back(t);
					it1++;
					continue;
				}
				else {
					if (tag[nr[v][it2].second]) {
						it2++;
						continue;
					} tag[nr[v][it2].second] = 1;
					nw.push_back(nr[v][it2]);
					it2++;
					continue;
				}
			}
			swap(nw, nr[v]);
			nw.clear();
			for (auto u : nr[v]) tag[u.second] = 0;
		}
	}
	
	for (int i = 0; i < q; ++i) {
		process();	
	}
	return 0;
}

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