oj.uz

Submission #686548

# Submission time Handle Problem Language Result Execution time Memory
686548 2023-01-25T12:29:08 Z ethening Robot (JOI21_ho_t4) C++17
100 / 100
 759 ms 155880 KB 
#include "bits/stdc++.h"
#include <queue>
#include <unordered_map>
using namespace std;
using ll = long long;
 
#define DEBUG 0
 
const ll INF = 1000'000'000'000'000'000ll;
 
const int MAXN = 100000;
const int MAXM = 200000;
 
int n, m;
 
unordered_map<int, int> s[MAXN + 5];
unordered_map<int, ll> csum[MAXN + 5];
 
int a[MAXM + 5][4];
 
struct edge {
	int fr;
	int to;
	ll weight;
} e[10 * MAXM + 5];
 
vector<int> v[10 * MAXM + 5];
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	int cnt = 0;
	
	s[1][0] = ++cnt;
	s[n][0] = ++cnt;

	int ecnt = 0;
 
	for (int i = 1; i <= m; i++) {
		cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3];
		if (s[a[i][0]].find(0) == s[a[i][0]].end()) {
			s[a[i][0]][0] = ++cnt;
		}
		if (s[a[i][0]].find(a[i][2]) == s[a[i][0]].end()) {
			s[a[i][0]][a[i][2]] = ++cnt;
			e[++ecnt] = {.fr = s[a[i][0]][0], .to = cnt, .weight = 0};
			v[s[a[i][0]][0]].push_back(ecnt);
		}
		if (csum[a[i][0]].find(a[i][2]) == csum[a[i][0]].end()) {
			csum[a[i][0]][a[i][2]] = a[i][3];
		}
		else csum[a[i][0]][a[i][2]] += a[i][3];
		if (s[a[i][1]].find(0) == s[a[i][1]].end()) {
			s[a[i][1]][0] = ++cnt;
		}
		if (s[a[i][1]].find(a[i][2]) == s[a[i][1]].end()) {
			s[a[i][1]][a[i][2]] = ++cnt;
			e[++ecnt] = {.fr = s[a[i][1]][0], .to = cnt, .weight = 0};
			v[s[a[i][1]][0]].push_back(ecnt);
		}
		if (csum[a[i][1]].find(a[i][2]) == csum[a[i][1]].end()) {
			csum[a[i][1]][a[i][2]] = a[i][3];
		}
		else csum[a[i][1]][a[i][2]] += a[i][3];
	}
 
	if (DEBUG) {
		for (int i = 1; i <= n; i++) {
			for (auto [dex, val] : s[i]) {
				cout << "i: " << i << " col: " << dex << " index: " << val << endl;
			}
		}
	}
 
	for (int i = 1; i <= m; i++) {
		int col = a[i][2];
		int fr = a[i][0];
		int to = a[i][1];
		int node10 = s[fr][0];
		int node1c = s[fr][col];
		int node20 = s[to][0];
		int node2c = s[to][col];
 
		e[++ecnt] = {.fr = node10, .to = node20, .weight = (ll)a[i][3]};
		v[node10].push_back(ecnt);
		e[++ecnt] = {.fr = node20, .to = node10, .weight = (ll)a[i][3]};
		v[node20].push_back(ecnt);
		
		e[++ecnt] = {.fr = node10, .to = node2c, .weight = 0};
		v[node10].push_back(ecnt);
		e[++ecnt] = {.fr = node20, .to = node1c, .weight = 0};
		v[node20].push_back(ecnt);
 
		e[++ecnt] = {.fr = node1c, .to = node20, .weight = csum[fr][col] - a[i][3]};
		v[node1c].push_back(ecnt);
		e[++ecnt] = {.fr = node2c, .to = node10, .weight = csum[to][col] - a[i][3]};
		v[node2c].push_back(ecnt);
		if (DEBUG) cout << ecnt << endl;
	}
 
	if (DEBUG) {
		for (int i = 1; i <= ecnt; i++) {
			cout << "fr: " << e[i].fr << " to: " << e[i].to << " we: " << e[i].weight << endl;
		}
	}
 
	// cout << "!!!" << cnt << " " << ecnt << endl;

	int source = s[1][0];
	int dest = s[n][0];
	vector<ll> dist(cnt + 5, INF);
	typedef pair<ll, int> pli;
	priority_queue<pli, vector<pli>, greater<pli>> Q;
	dist[source] = 0;
	Q.push({0, source});
	while (!Q.empty()) {
		auto [curDist, cur] = Q.top();
		Q.pop();
		if (dist[cur] < curDist) continue;
		if (cur == dest) break;
		for (auto eg: v[cur]) {
			if (dist[cur] + e[eg].weight < dist[e[eg].to]) {
				dist[e[eg].to] = dist[cur] + e[eg].weight;
				Q.push({dist[e[eg].to], e[eg].to});
			}
		}
	}
	if (DEBUG) {
		for (int i = 1; i <= cnt; i++) {
			cout << "dist " << i << " : " << dist[i] << endl;
		}
	}
 
	if (DEBUG) {
		cout << "DEST: " << dest << endl;
	}
 
	if (dist[dest] == INF) dist[dest] = -1;
	cout << dist[dest] << "\n";
}

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 58324 KB Output is correct
2 Correct 27 ms 58260 KB Output is correct
3 Correct 28 ms 58208 KB Output is correct
4 Correct 28 ms 58160 KB Output is correct
5 Correct 29 ms 58256 KB Output is correct
6 Correct 27 ms 58196 KB Output is correct
7 Correct 30 ms 58384 KB Output is correct
8 Correct 28 ms 58264 KB Output is correct
9 Correct 30 ms 59220 KB Output is correct
10 Correct 30 ms 59092 KB Output is correct
11 Correct 30 ms 59036 KB Output is correct
12 Correct 29 ms 58956 KB Output is correct
13 Correct 30 ms 59028 KB Output is correct
14 Correct 29 ms 59072 KB Output is correct
15 Correct 28 ms 58736 KB Output is correct
16 Correct 30 ms 59008 KB Output is correct
17 Correct 29 ms 58820 KB Output is correct
18 Correct 29 ms 58540 KB Output is correct
19 Correct 28 ms 58588 KB Output is correct
20 Correct 29 ms 58800 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 85656 KB Output is correct
2 Correct 118 ms 72476 KB Output is correct
3 Correct 195 ms 87304 KB Output is correct
4 Correct 125 ms 77956 KB Output is correct
5 Correct 640 ms 151028 KB Output is correct
6 Correct 591 ms 142360 KB Output is correct
7 Correct 404 ms 130764 KB Output is correct
8 Correct 515 ms 127216 KB Output is correct
9 Correct 520 ms 127316 KB Output is correct
10 Correct 398 ms 105448 KB Output is correct
11 Correct 293 ms 101620 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 58324 KB Output is correct
2 Correct 27 ms 58260 KB Output is correct
3 Correct 28 ms 58208 KB Output is correct
4 Correct 28 ms 58160 KB Output is correct
5 Correct 29 ms 58256 KB Output is correct
6 Correct 27 ms 58196 KB Output is correct
7 Correct 30 ms 58384 KB Output is correct
8 Correct 28 ms 58264 KB Output is correct
9 Correct 30 ms 59220 KB Output is correct
10 Correct 30 ms 59092 KB Output is correct
11 Correct 30 ms 59036 KB Output is correct
12 Correct 29 ms 58956 KB Output is correct
13 Correct 30 ms 59028 KB Output is correct
14 Correct 29 ms 59072 KB Output is correct
15 Correct 28 ms 58736 KB Output is correct
16 Correct 30 ms 59008 KB Output is correct
17 Correct 29 ms 58820 KB Output is correct
18 Correct 29 ms 58540 KB Output is correct
19 Correct 28 ms 58588 KB Output is correct
20 Correct 29 ms 58800 KB Output is correct
21 Correct 211 ms 85656 KB Output is correct
22 Correct 118 ms 72476 KB Output is correct
23 Correct 195 ms 87304 KB Output is correct
24 Correct 125 ms 77956 KB Output is correct
25 Correct 640 ms 151028 KB Output is correct
26 Correct 591 ms 142360 KB Output is correct
27 Correct 404 ms 130764 KB Output is correct
28 Correct 515 ms 127216 KB Output is correct
29 Correct 520 ms 127316 KB Output is correct
30 Correct 398 ms 105448 KB Output is correct
31 Correct 293 ms 101620 KB Output is correct
32 Correct 154 ms 82248 KB Output is correct
33 Correct 208 ms 85904 KB Output is correct
34 Correct 415 ms 104948 KB Output is correct
35 Correct 312 ms 97528 KB Output is correct
36 Correct 394 ms 118060 KB Output is correct
37 Correct 448 ms 125708 KB Output is correct
38 Correct 480 ms 135012 KB Output is correct
39 Correct 280 ms 90604 KB Output is correct
40 Correct 636 ms 127312 KB Output is correct
41 Correct 599 ms 127388 KB Output is correct
42 Correct 596 ms 128288 KB Output is correct
43 Correct 266 ms 88720 KB Output is correct
44 Correct 428 ms 98336 KB Output is correct
45 Correct 453 ms 119568 KB Output is correct
46 Correct 399 ms 116896 KB Output is correct
47 Correct 415 ms 122224 KB Output is correct
48 Correct 759 ms 155880 KB Output is correct