Submission #1268170

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268170		MateiKing80	Board Game (JOI24_boardgame)	C++20	29 / 100	4086 ms	4980 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int inf = 2e9;

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

//DE BAGAT LL

signed main() {
	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);
	for (int rep = 0; rep <= nrStop; rep ++) {
		int sum = 0;
		for (int i = 1; i < k; i ++) {
			sum += dp[start[i]];
		}
		for (int i = 0; i < n; i ++)
			ans[i] = min(ans[i], distStart[i] + sum);
		//recalc distStart
		auto distStart2 = distStart;
		priority_queue<pii> pq;
		for (int i = 0; i < n; i ++)
			pq.push({-distStart[i], i});
		viz.assign(n, 0);
		while (!pq.empty()) {
			auto x = pq.top();
			pq.pop();
			if (viz[x.sc])
				continue;
			viz[x.sc] = true;
			x.fr *= -1;
			distStart2[x.sc] = x.fr;
			for (auto i : vec[x.sc]) {
				int nw = 1;
				if (stop[x.sc])
					nw += distStart[x.sc];
				else
					nw += distStart2[x.sc];
				if (distStart2[i] > nw) {
					distStart2[i] = nw;
					pq.push({-nw, i});
				}
			}
		}
		distStart = distStart2;
		//recalc dp
		if (rep == 0)
			for (int i = 0; i < n; i ++)
				if (!stop[i])
					dp[i] = inf;
		vector<int> dp2(n, inf);
		for (int i = 0; i < n; i ++) {
			if (!stop[i])
				continue;
			for (auto j : vec[i])
				pq.push({-dp[i] - 1, j});
		}
		viz.assign(n, 0);
		while (!pq.empty()) {
			auto x = pq.top();
			pq.pop();
			if (viz[x.sc])
				continue;
			viz[x.sc] = true;
			x.fr *= -1;
			dp2[x.sc] = x.fr;
			if (!stop[x.sc]) {
				for (auto i : vec[x.sc]) {
					int nw = x.fr + 1;
					if (dp2[i] > nw) {
						dp2[i] = nw;
						pq.push({-nw, i});
					}
				}
			}
		}
		dp = dp2;
	}
	for (int i = 0; i < n; i ++)
		cout << ans[i] << '\n';
}

/*
imi trebuie un dp de tipul: pentru fiecare casuta stii numarul minim de operatii tipul 1 necesar
acum tu poti veni de la oricare alta casuta pe o ruta fara stop-uri
*/

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