oj.uz

Submission #770107

# Submission time Handle Problem Language Result Execution time Memory
770107 2023-06-30T18:46:18 Z mgl_diamond Robot (JOI21_ho_t4) C++14
100 / 100
 796 ms 84312 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const ll INF = 1e18;

struct Edge {
	int to, c;
	ll p;
};

map<int, vector<Edge>> graph[100001];
ll dp[100001];
map<int, ll> dp2[100001], psum[100001];

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v, c;
		ll p;
		cin >> u >> v >> c >> p;
		graph[u][c].push_back({v, c, p});
		graph[v][c].push_back({u, c, p});
		psum[u][c] += p;
		psum[v][c] += p;
	}

	memset(dp, 0x3f, sizeof dp);
	dp[1] = 0;
	priority_queue<tuple<ll, int, int>> pq;
	pq.push({0, 1, 0});
	while (pq.size()) {
		ll cost;
		int node, c;
		tie(cost, node, c) = pq.top();
		pq.pop();

		if (c) {
			if (dp2[node][c] != -cost) continue;
			for (Edge i : graph[node][c]) {
				// We can't flip i in this case
				ll case1 = psum[node][c] - i.p;
				if (case1 - cost < dp[i.to]) {
					dp[i.to] = case1 - cost;
					pq.push({-dp[i.to], i.to, 0});
				}
			}
		} else {
			if (dp[node] != -cost) continue;
			for (auto &i : graph[node]) {
				for (Edge j : i.second) {
					// Case 1: We don't flip j
					ll case1 = psum[node][j.c] - j.p - cost;
					if (case1 < dp[j.to]) {
						dp[j.to] = case1;
						pq.push({-dp[j.to], j.to, 0});
					}
					// Case 2: We flip j but not another edge of the same colour
					ll case2 = j.p - cost;
					if (case2 < dp[j.to]) {
						dp[j.to] = case2;
						pq.push({-dp[j.to], j.to, 0});
					}
					// Case 3: We flip j and another edge of the same colour
					ll case3 = -cost;
					if (!dp2[j.to].count(j.c) || case3 < dp2[j.to][j.c]) {
						dp2[j.to][j.c] = case3;
						pq.push({-dp2[j.to][j.c], j.to, j.c});
					}
				}
			}
		}
	}
	cout << (dp[n] > INF ? -1 : dp[n]);
	return 0;
}

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15188 KB Output is correct
2 Correct 7 ms 15192 KB Output is correct
3 Correct 7 ms 15188 KB Output is correct
4 Correct 7 ms 15188 KB Output is correct
5 Correct 7 ms 15188 KB Output is correct
6 Correct 7 ms 15188 KB Output is correct
7 Correct 8 ms 15316 KB Output is correct
8 Correct 7 ms 15188 KB Output is correct
9 Correct 10 ms 15828 KB Output is correct
10 Correct 9 ms 15700 KB Output is correct
11 Correct 8 ms 15440 KB Output is correct
12 Correct 9 ms 15524 KB Output is correct
13 Correct 9 ms 15440 KB Output is correct
14 Correct 9 ms 15444 KB Output is correct
15 Correct 8 ms 15420 KB Output is correct
16 Correct 8 ms 15444 KB Output is correct
17 Correct 8 ms 15444 KB Output is correct
18 Correct 8 ms 15316 KB Output is correct
19 Correct 9 ms 15316 KB Output is correct
20 Correct 8 ms 15436 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 33600 KB Output is correct
2 Correct 62 ms 24628 KB Output is correct
3 Correct 114 ms 29676 KB Output is correct
4 Correct 85 ms 27292 KB Output is correct
5 Correct 758 ms 78980 KB Output is correct
6 Correct 562 ms 71960 KB Output is correct
7 Correct 266 ms 56320 KB Output is correct
8 Correct 308 ms 50884 KB Output is correct
9 Correct 331 ms 50960 KB Output is correct
10 Correct 239 ms 48132 KB Output is correct
11 Correct 96 ms 32716 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15188 KB Output is correct
2 Correct 7 ms 15192 KB Output is correct
3 Correct 7 ms 15188 KB Output is correct
4 Correct 7 ms 15188 KB Output is correct
5 Correct 7 ms 15188 KB Output is correct
6 Correct 7 ms 15188 KB Output is correct
7 Correct 8 ms 15316 KB Output is correct
8 Correct 7 ms 15188 KB Output is correct
9 Correct 10 ms 15828 KB Output is correct
10 Correct 9 ms 15700 KB Output is correct
11 Correct 8 ms 15440 KB Output is correct
12 Correct 9 ms 15524 KB Output is correct
13 Correct 9 ms 15440 KB Output is correct
14 Correct 9 ms 15444 KB Output is correct
15 Correct 8 ms 15420 KB Output is correct
16 Correct 8 ms 15444 KB Output is correct
17 Correct 8 ms 15444 KB Output is correct
18 Correct 8 ms 15316 KB Output is correct
19 Correct 9 ms 15316 KB Output is correct
20 Correct 8 ms 15436 KB Output is correct
21 Correct 123 ms 33600 KB Output is correct
22 Correct 62 ms 24628 KB Output is correct
23 Correct 114 ms 29676 KB Output is correct
24 Correct 85 ms 27292 KB Output is correct
25 Correct 758 ms 78980 KB Output is correct
26 Correct 562 ms 71960 KB Output is correct
27 Correct 266 ms 56320 KB Output is correct
28 Correct 308 ms 50884 KB Output is correct
29 Correct 331 ms 50960 KB Output is correct
30 Correct 239 ms 48132 KB Output is correct
31 Correct 96 ms 32716 KB Output is correct
32 Correct 101 ms 29096 KB Output is correct
33 Correct 101 ms 29868 KB Output is correct
34 Correct 291 ms 50608 KB Output is correct
35 Correct 219 ms 41952 KB Output is correct
36 Correct 251 ms 46912 KB Output is correct
37 Correct 308 ms 49112 KB Output is correct
38 Correct 269 ms 55588 KB Output is correct
39 Correct 94 ms 32496 KB Output is correct
40 Correct 314 ms 52172 KB Output is correct
41 Correct 345 ms 52428 KB Output is correct
42 Correct 400 ms 60796 KB Output is correct
43 Correct 145 ms 37488 KB Output is correct
44 Correct 249 ms 43380 KB Output is correct
45 Correct 246 ms 47568 KB Output is correct
46 Correct 210 ms 47992 KB Output is correct
47 Correct 266 ms 49076 KB Output is correct
48 Correct 796 ms 84312 KB Output is correct