Submission #1270087

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270087		MateiKing80	Board Game (JOI24_boardgame)	C++20	36 / 100	4090 ms	8236 KiB

Main

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define int ll

const int inf = 2e15;

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;
	
	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> deLa2La1(n);
	for (int i = 0; i < n; i ++) {
		deLa2La1[i] = init2[i] - init[i] + 2;
	}
	
	
	for (int rep = 0; rep <= nrStop; rep ++) {
		int sum = 0;
		for (int i = 1; i < k; i ++)
			if (rep != 0)
				sum += min(init[start[i]] + 2 * (rep - 1), init2[start[i]] + rep);
		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;
	}
	for (int i = 0; i < n; i ++)
		cout << ans[i] << '\n';
}

/*
6 9 2
1 2
2 3
2 4
2 5
3 6
3 4
1 4
4 5
1 5
111100
5 6 

am 2 variante
ma duc la cel mai apropiat stop:
acum trebuie sa vad astfel:
pentru varianta in care fac 2 de fiecare data ma costa init + 2 * (nrture - 1) = init2+ 1 * (nrture - tureFacute);
                                                       nrture = init2 - tureFacute - init + 2		
vrem init2 - tureFacute minim
si   init minim

.......X....XX
...X

*/

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