Submission #1270158

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270158		MateiKing80	Board Game (JOI24_boardgame)	C++20	88 / 100	1729 ms	171432 KiB

Main

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define int ll

const int inf = 1e18;
const int BULAN = 100;

using pii = pair<int, int>;
#define fr first
#define sc second



signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n, m, k;
	cin >> n >> m >> k;
	vector<vector<int>> vec(n);
	vector<bool> stop(n);
	for (int i = 0; i < m; i ++) {
		int u, v;
		cin >> u >> v;
		u --, v --;
		vec[u].push_back(v);
		vec[v].push_back(u);
	}
	int nrStop = 0;
	for (int i = 0; i < n; i ++) {
		char ch;
		cin >> ch;
		stop[i] = ch - '0';
		nrStop += stop[i];
	}
	vector<int> start(k);
	for (int i = 0; i < k; i ++) {
		cin >> start[i];
		start[i] --;
	}
	vector<int> distStart(n, inf), dp(n, 0);
	distStart[start[0]] = 0;
	queue<int> st;
	st.push(start[0]);
	vector<bool> viz(n, false);
	while (!st.empty()) {
		int x = st.front();
		st.pop();
		if ((x != start[0] && stop[x]) || viz[x])
			continue;
		viz[x] = true;
		for (auto i : vec[x]) {
			distStart[i] = min(distStart[i], 1 + distStart[x]);
			st.push(i);
		}
	}
	vector<int> ans(n, inf);
	
	vector<bool> doubleStop(n, false);
	for (int i = 0; i < n; i ++) {
		for (auto j : vec[i])
			if (stop[i] && stop[j])
				doubleStop[i] = true;
	}
	
	vector<int> init(n, inf);
	for (int i = 0; i < n; i ++)
		if (stop[i]) {
			st.push(i);
			init[i] = 0;
		}
	viz.assign(n, 0);
	while (!st.empty()) {
		int x = st.front();
		st.pop();
		if (viz[x])
			continue;
		viz[x] = true;
		for (auto i : vec[x]) {
			init[i] = min(init[i], init[x] + 1);
			st.push(i);
		}
	}
	
	for (auto &i : init)
		if (i == 0)
			i += 2;
	for (int i = 0; i < n; i ++)
		if (doubleStop[i])
			init[i] --;
	
	deque<int> dq;
	vector<int> init2(n, inf);
	
	for (int i = 0; i < n; i ++)
		if (doubleStop[i]) {
			init2[i] = 0;
			dq.push_back(i);
		}
	viz.assign(n, 0);
	while (!dq.empty()) {
		int x = dq.front();
		dq.pop_front();
		if (viz[x])
			continue;
		viz[x] = true;
		for (auto i : vec[x]) {
			int cost = (stop[x] == 0);
			init2[i] = min(init2[i], init2[x] + cost);
			if (cost)
				dq.push_back(i);
			else
				dq.push_front(i);
		}
	}
	
	vector<int> schimb;
	for (int i = 1; i < k; i ++)
		schimb.push_back(init2[start[i]] - init[start[i]] + 2);
	int add = 2 * (k - 1), point = 0;
	sort(schimb.begin(), schimb.end());
	int sum = 0;
	vector<int> cost(n + 1);
	for (int rep = 0; rep <= n; rep ++) {
		if (rep == 1)
			for (int i = 1; i < k; i ++)
				sum += init[start[i]];
		if (rep > 1)
			sum += add;
		if (rep >= 1) {
			while (point < (int)schimb.size() && schimb[point] <= rep) {
				add --;
				point ++;
			}
		}
		cost[rep] = sum;
	}

	for (int i = 0; i < n; i ++)
		ans[i] = min(ans[i], distStart[i]);
	
	if (k <= BULAN) {
		for (int cst = k; cst <= 2 * k - 1; cst ++) {
			priority_queue<pair<int, int>> pq;
			pq.push({0, start[0]});
			vector<pair<int, int>> dist(n, {inf, 0});
			dist[start[0]] = {0, 0};
			viz.assign(n, 0);
			while (!pq.empty()) {
				int x = pq.top().second;
				pq.pop();
				if (viz[x])
					continue;
				viz[x] = true;
				for (auto i : vec[x]) {
					if (stop[x] && x != start[0]) {
						dist[i] = min(dist[i], {dist[x].first + cst, dist[x].second + 1});
					} else {
						dist[i] = min(dist[i], {dist[x].first + 1, dist[x].second});
					}
					pq.push({-dist[i].first, i});
				}
			}
			for (int i = 0; i < n; i ++)
				ans[i] = min(ans[i], cost[dist[i].second] + dist[i].first - (cst - 1) * dist[i].second);
		}
	} else {
		dq.clear();
		dq.push_back(start[0]);
		vector<int> dist(n, inf);
		dist[start[0]] = 0;
		viz.assign(n, 0);
		while (!dq.empty()) {
			int x = dq.front();
			dq.pop_front();
			if (viz[x])
				continue;
			viz[x] = true;
			for (auto i : vec[x]) {
				if (stop[x] && x != start[0]) {
					dist[i] = min(dist[i], dist[x] + 1);
					dq.push_back(i);
				} else {
					dist[i] = min(dist[i], dist[x]);
					dq.push_front(i);
				}
			}
		}
		int upper = n / (k - 1) + 1;
		queue<pair<int, int>> q;
		q.push({start[0], 0});
		vector<vector<int>> dst(n, vector<int> (upper, inf));
		dst[start[0]][0] = 0;
		vector<vector<bool>> vz(n, vector<bool> (upper, false));
		while (!q.empty()) {
			int nod = q.front().first;
			int nrx = q.front().second;
			q.pop();
			if (vz[nod][nrx - dist[nod]])
				continue;
			vz[nod][nrx - dist[nod]] = true;
			for (auto i : vec[nod]) {
				if (stop[nod] && nod != start[0]) {
					if (nrx + 1 < dist[i] + upper) {
						dst[i][nrx + 1 - dist[i]] = min(dst[i][nrx + 1 - dist[i]], dst[nod][nrx - dist[nod]] + 1);
						q.push({i, nrx + 1});
					}
				} else {
					if (nrx < dist[i] + upper) {
						dst[i][nrx - dist[i]] = min(dst[i][nrx - dist[i]], dst[nod][nrx - dist[nod]] + 1);
						q.push({i, nrx});
					}
				}
			}
		}
		for (int i = 0; i < n; i ++)
			for (int j = 0; j < upper; j ++)
				if (j + dist[i] <= n)
					ans[i] = min(ans[i], cost[j + dist[i]] + dst[i][j]);
	}
	for (int i = 0; i < n; i ++)
		cout << ans[i] << '\n';
}

• Subtask 1: 0 / 3
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 19 / 19
• Subtask 5: 23 / 23
• Subtask 6: 9 / 9
• Subtask 7: 23 / 23
• Subtask 8: 0 / 9