Submission #1234355

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234355		hashdfdfh	Bitaro’s Party (JOI18_bitaro)	C++20	7 / 100	2110 ms	411304 KiB

bitaro

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

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

// 保存原始边信息
vector<int> edges[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;
		}

		// 因为边肯定小->大， 直接遍历就可以
		for (int u = 1; u <= n; u++) {
			// 如果没有被禁用，但是仍然是-1的，认为是0
			if (!tag[u] && dist[u] == -1) {
				dist[u] = 0;
			}

			// 如果仍然是-1的，说明不可达
			if (dist[u] == -1) {
				continue;
			}
			for (auto v : edges[u]) {
				dist[v] = max(dist[v], dist[u] + 1);
			}
		}
		cout << dist[start] << 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;
	}
}

// 把u的结果，合并到v上
void merge(int u, int v) {
	// 重置
	memset(tag, false, sizeof(tag));

	vector<pair<int, int>> nw;

	// maxb[u]和maxb[v]中遍历到的位置
	int idx1 = 0, idx2 = 0;

	while (idx1 < maxb[u].size() && idx2 < maxb[v].size()) {
		// 如果左侧比较大
		if (maxb[u][idx1].first + 1 > maxb[v][idx2].first) {
			// 如果已经算进去过
			if (tag[maxb[u][idx1].second]) {
				idx1++;
				continue;
			}

			// 进入进来
			tag[maxb[u][idx1].second] = 1;

			// 个数要+1
			auto t = maxb[u][idx1];
			t.first++;
			nw.push_back(t);
			idx1++;
		}
		else {
			// 如果已经算进去过
			if (tag[maxb[v][idx2].second]) {
				idx2++;
				continue;
			}

			// 加入进来
			tag[maxb[v][idx2].second] = 1;
			nw.push_back(maxb[v][idx2]);
			idx2++;
		}

		// 如果已经到达BASE
		if (nw.size() == BASE) {
			break;
		}
	}

	// 如果还没有到BASE个
	if (nw.size() < BASE) {
		// 如果maxb[v]还没有遍历结束
		while (idx2 < maxb[v].size()) {
			// 如果已经算进去过
			if (tag[maxb[v][idx2].second]) {
				idx2++;
				continue;
			}

			// 否则加进来
			tag[maxb[v][idx2].second] = 1;
			nw.push_back(maxb[v][idx2]);
			idx2++;

			// 如果已经到达BASE
			if (nw.size() == BASE) {
				break;
			}
		}

		// 如果maxb[u]还没有遍历结束
		while (idx1 < maxb[u].size()) {
			// 如果已经算进去过
			if (tag[maxb[u][idx1].second]) {
				idx1++;
				continue;
			}

			// 否则加进来
			tag[maxb[u][idx1].second] = 1;

			// 加进来前要长度+1
			auto t = maxb[u][idx1];
			t.first++;
			nw.push_back(t);
			idx1++;

			// 如果已经到达BASE
			if (nw.size() == BASE) {
				break;
			}
		}
	}

	swap(nw, maxb[v]);
}

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

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

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

	for (int u = 1; u <= n; u++) {
		// 如果目前个数小于BASE，那么吧自己放进去
		if (maxb[u].size() < BASE) {
			maxb[u].push_back(make_pair(0, u));
		}

		for (auto v : edges[u]) {
			merge(u, v);
		}
	}

	for (int i = 0; i < q; ++i) {
		process();
	}
	return 0;
}

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