Submission #1206723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206723		pedroslrey	Board Game (JOI24_boardgame)	C++20	40 / 100	812 ms	29232 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using graph = vector<vector<int>>;
using lli = long long;

tuple<lli, int, vector<int>> calc_slopes(graph &G, vector<bool> &red, vector<int> &frens) {
	int n = G.size();

	vector<int> dist2(n, -1);
	{
		queue<int> q;
		for (int i = 0; i < n; ++i) if (red[i]) {
			q.push(i);
			dist2[i] = 0;
		}

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

			for (int v: G[u]) if (dist2[v] == -1) {
				dist2[v] = dist2[u] + 1;
				q.push(v);
			}
		}
	}

	vector<int> dist1(n, -1);
	{
		deque<int> q;
		for (int i = 0; i < n; ++i) if (red[i]) {
			bool ok = false;
			for (int v: G[i]) if (red[v])
				ok = true;

			if (ok) {
				dist1[i] = 0;
				q.push_back(i);
			}
		}

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

			for (int v: G[u]) if (dist1[v] > dist1[u] + !red[u] || dist1[v] == -1)
				if (red[u]) { dist1[v] = dist1[u]; q.push_front(v); }
				else { dist1[v] = dist1[u] + 1; q.push_back(v); }
		}
	}

	lli c0 = 0;
	vector<int> slopes; int sl = 0;
	for (int f: frens) {
		if (dist2[f] == 0) dist2[f] = (dist1[f] == 0 ? 1 : 2);
		c0 += dist2[f];
		++sl;
		// cerr << f << " -> " << dist1[f] << " " << dist2[f] << "\n";
		if (dist1[f] != -1 && dist1[f] - dist2[f] + 2 > 1) {
			slopes.push_back(dist1[f] - dist2[f] + 2);
			++sl;
		}
		if (dist1[f] == -1) ++sl;
	}

	// cerr << c0 << " " << sl << "\n";

	sort(slopes.begin(), slopes.end());

	return {c0, sl, slopes};
}

vector<vector<int>> calc_dists(graph &G, int s, vector<bool> &red, int mx) {
	int n = G.size();
	vector<vector<int>> dist(n, vector<int>(mx, -1));

	queue<pair<int, int>> q;
	q.emplace(s, 0);
	dist[s][0] = 0;

	while (!q.empty()) {
		auto [u, k] = q.front(); q.pop();

		for (int v: G[u]) if (k + red[v] < mx && dist[v][k + red[v]] == -1) {
			q.emplace(v, k + red[v]);
			dist[v][k + red[v]] = dist[u][k] + 1;
		}
	}

	return dist;
}

vector<lli> calc_dists2(graph &G, int st, vector<bool> &red, int a) {
	int n = G.size();
	vector<vector<lli>> dist(n, vector<lli>(2, 1e18));

	set<tuple<lli, int, int>> s;
	s.emplace(dist[st][0] = 0, st, 0);

	vector<vector<bool>> marc(n, vector<bool>(2));
	while (!s.empty()) {
		auto [d, u, b] = *s.begin(); s.erase(s.begin());

		if (marc[u][b]) continue;
		marc[u][b] = true;

		int k = 1 + (u != st ? a*red[u] : 0);
		int nb = b || (u != st ? red[u] : false);

		for (int v: G[u]) if (dist[v][nb] > d + k)
			s.emplace(dist[v][nb] = d + k, v, nb);
	}
	
	vector<lli> ans(n);
	for (int i = 0; i < n; ++i)
		ans[i] = dist[i][1];

	return ans;
}

vector<int> calc_mn(graph &G, int s, vector<bool> &red) {
	int n = G.size();

	vector<int> dist(n, -1);

	deque<int> q;
	q.push_back(s);
	dist[s] = 0;

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

		for (int v: G[u]) if (dist[v] == -1 || dist[v] > dist[u] + red[v])
			if (red[v]) { dist[v] = dist[u] + 1; q.push_back(v); }
			else { dist[v] = dist[u]; q.push_front(v); }
	}

	return dist;
}

vector<vector<int>> calc_dists3(graph &G, int s, vector<bool> &red, vector<int> &mn, int mx) {
	int n = G.size();
	vector<vector<int>> dist(n, vector<int>(mx, -1));

	queue<pair<int, int>> q;
	q.emplace(s, 0);
	dist[s][0] = 0;

	while (!q.empty()) {
		auto [u, k] = q.front(); q.pop();

		for (int v: G[u]) {
			int d = k + red[v] - mn[v] + mn[u];
			if (d < mx && dist[v][d] == -1) {
				q.emplace(v, d);
				dist[v][d] = dist[u][k] + 1;
			}
		}
	}

	return dist;
}

int main() {
	int n, m, p;
	cin >> n >> m >> p;

	graph G(n);
	for (int i = 0; i < m; ++i) {
		int u, v;
		cin >> u >> v;

		--u; --v;
		G[u].push_back(v);
		G[v].push_back(u);
	}

	vector<bool> red(n); bool ok = false;
	for (int i = 0; i < n; ++i) {
		char c;
		cin >> c; red[i] = c - '0';

		ok = ok || red[i];
	}

	int s;
	cin >> s;
	--s;

	if (!ok) {
		vector<vector<int>> dist = calc_dists(G, s, red, 1);

		for (int i = 0; i < n; ++i)
			cout << dist[i][0] << " ";
		cout << "\n";
		return 0;
	}
	
	--p;
	vector<int> frens(p);
	for (int &f: frens) {
		cin >> f;
		--f;
	}

	auto [c0, sl, slopes] = calc_slopes(G, red, frens);

	vector<lli> ans(n, 1e18);
	{
		vector<vector<int>> dist = calc_dists(G, s, red, 2);

		for (int u = 0; u < n; ++u)
			if (!red[u] && dist[u][0] != -1)
				ans[u] = min(ans[u], 1LL*dist[u][0]);
			else if (red[u] && dist[u][1] != -1)
				ans[u] = min(ans[u], 1LL*dist[u][1]);

		ans[s] = 0;
	}

	if  (p > sqrt(n)) {
		int mx = n/p + 5;

		vector<int> mn = calc_mn(G, s, red);
		vector<vector<int>> dist = calc_dists3(G, s, red, mn, mx);
	
		vector<lli> costs(n);	
		int j = 0; int cur = sl; lli c = c0;
		for (int i = 1; i < n; ++i) {
			while (j < slopes.size() && slopes[j] <= i) { ++j; --cur; }
			costs[i] = c;
			c += cur;
		}

		for (int u = 0; u < n; ++u) {
			for (int i = mn[u] - red[u]; i < min(mn[u] - red[u] + mx, n); ++i)
				if (!red[u] && dist[u][i - mn[u]] != -1)
					ans[u] = min(ans[u], costs[i] + dist[u][i - mn[u]]);
				else if (red[u] && i + 1 - mn[u] < mx && dist[u][i + 1 - mn[u]] != -1)
					ans[u] = min(ans[u], costs[i] + dist[u][i + 1 - mn[u]]);
		}
	}
	else {
		{
			vector<lli> dist = calc_dists2(G, s, red, sl);

			for (int u = 0; u < n; ++u) {
				// cerr << c0 - sl + dist[u] << "\n";
				ans[u] = min(ans[u], c0 - sl + dist[u]);
			}
		}
		int cur = sl; lli c = c0; int lst = 1;
		for (int x: slopes) {
			// cerr << x << " cost = " << c << "\n";
			c += 1LL*cur*(x - lst);
			--cur;

			vector<lli> dist = calc_dists2(G, s, red, cur);

			for (int u = 0; u < n; ++u)
				ans[u] = min(ans[u], c - 1LL*cur*x + dist[u]);
		}
	}

	for (lli x: ans)
		cout << x << " ";
	cout << "\n";	
}

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