Submission #1234303

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234303		hashdfdfh	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	5 ms	8776 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];
// 保存入度信息
int in2[MAX_N];

// 保存和u距离 最远的BASE个node信息
// first：距离
// second：节点编号
vector<pair<int, int>> maxb[MAX_N];

// 保存到u的最远距离
int dist[MAX_N];

// 0表示可用，1表示被禁止
int tag[MAX_N];

int n, m, q;

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

	// 如果禁用比较多
	if (y >= BASE) {
		// 初始化距离为-1
		memset(dist, -1, sizeof(dist));
		memset(tag, 0, sizeof(tag));

		// 读取y个禁用点
		for (int i = 0; i < y; i++) {
			int x;
			cin >> x;
			tag[x] = 1;
		}

		// 在颠倒图中进行拓扑排序
		queue<int> q;
		for (int i = 1; i <= n; ++i) {
			if (in2[i] == 0) {
				q.push(i);
			}
		}
		// 初始化start
		dist[start] = 0;

		while (!q.empty()) {
			int u = q.front();
			q.pop();

			for (int v : edges2[u]) {
				// 如果v被禁用
				if (tag[v]) {
					continue;
				}

				in2[v]--;
				// 更新dist
				if (dist[u] >= 0) {
					dist[v] = max(dist[v], dist[u] + 1);
				}

				// 如果入度为0
				if (in2[v] == 0) {
					q.push(v);
				}
			}
		}

		// 统计结果
		int ans = -1;
		for (int i = 1; i <= n; ++i) {
			if (!tag[i]) {
				ans = max(ans, dist[i]);
			}
		}
		cout << ans << endl;
	}
	// 如果禁用比较少
	else {
		memset(tag, 0, sizeof(tag));

		// 读取y个禁用点
		for (int i = 0; i < y; i++) {
			int x;
			cin >> x;
			tag[x] = 1;
		}
		
		int maxv = -1;
		
		// 遍历和start最远的BASE个
		for (auto v : maxb[start]) {
			// 如果没有被禁用掉
			if (!tag[v.second]) {
				maxv = v.first;
				break;
			}
		}

		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);
		in2[u]++;
	}

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

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