Submission #1206681

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206681		pedroslrey	Board Game (JOI24_boardgame)	C++20	3 / 100	4097 ms	1114112 KiB

Main

#include <bits/stdc++.h>

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

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;
}

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;
	}

	vector<vector<int>> dists = calc_dists(G, s, red, n + 1);

	vector<lli> costs(n + 1);
	for (int f: frens) {
		vector<vector<int>> dist = calc_dists(G, f, red, n + 1);
		for (int i = 1; i <= n; ++i) {
			int mn = 1e9;
			for (int j = 0; j < n; ++j) if (red[j])
				if (dist[j][i] != -1) mn = min(mn, dist[j][i]);

			if (mn != 1e9) costs[i] += mn;
			else costs[i] = 1e18;
		}
	}

	for (int i = 0; i < n; ++i) {
		lli mn = 1e18;
		if (!red[i] || i == s) {
			for (int j = 0; j <= n; ++j) if (dists[i][j] != -1)
				mn = min(mn, dists[i][j] + costs[j]);
		}
		else {
			for (int j = 1; j <= n; ++j) if (dists[i][j] != -1)
				mn = min(mn, dists[i][j] + costs[j-1]);
		}

		cout << mn << "\n";
	}
}

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