Submission #1270095

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270095		MateiKing80	Board Game (JOI24_boardgame)	C++20	0 / 100	4094 ms	7236 KiB

Main

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define int ll

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

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 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}); //tine costul si numarul de x prin care am trecut
			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});
				}
			} //in principiu pe mine ma costa cand plec dintr-un x daca acesta nu este start[0]
			for (int i = 0; i < n; i ++) {
				ans[i] = min(ans[i], cost[dist[i].second] + dist[i].first - (cst - 1) * dist[i].second);
			}
		}
	
	for (int i = 0; i < n; i ++)
		cout << ans[i] << '\n';
}

/*

am acum corect facuti timpii la care se schimba
pentru k mic fac for de la 2 * k la k
si trebuie sa pun cost pe o muchie catre un x fiecare indice
vad cat vine costu la fiecare si testez valorile alea
ar trebui sa fie ok

*/

• Subtask 1: 0 / 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