oj.uz

Submission #415943

# Submission time Handle Problem Language Result Execution time Memory
415943 2021-06-01T17:52:56 Z egod1537 Robot (JOI21_ho_t4) C++14
100 / 100
 819 ms 99044 KB 
#include <bits/stdc++.h>
#include <unordered_map>

using namespace std;
typedef long long ll;
struct Line {
	int to, col;
	ll cost;
	int cc;
};
struct Q {
	int pos;
	ll cost;
};
bool operator<(const Q& a, const Q& b) {
	return a.cost > b.cost;
}

vector<vector<Line>> V;

vector<vector<int>> vc;
vector<vector<int>> vidx;

vector<vector<vector<Line>>> vcole;
vector<vector<int>> colcnt;
vector<vector<ll>> colsum;

vector<ll> dst;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	int n, m; cin >> n >> m;
	V.resize(n + 1);
	colcnt.resize(n + 1); colsum.resize(n + 1);
	vcole.resize(n + 1); vidx.resize(n + 1);
	vc.resize(n + 1);
	int vnum = n + 1;
	for (int i = 0; i < m; i++) {
		int from, to, col; ll cost; cin >> from >> to >> col >> cost;
		vc[from].push_back(col);
		vc[to].push_back(col);
		V[from].push_back({ to, col, cost });
		V[to].push_back({ from, col, cost });
	}

	for (int i = 1; i <= n; i++) {
		vector<int>& v = vc[i];
		sort(v.begin(), v.end());
		v.erase(unique(v.begin(), v.end()), v.end());

		int sz = v.size();
		vidx[i].resize(sz); colcnt[i].resize(sz);
		colsum[i].resize(sz); vcole[i].resize(sz);
		for (int& w : vidx[i]) w = vnum++;

		for (Line& w : V[i]) {
			int fromc = lower_bound(v.begin(), v.end(), w.col) - v.begin();
			colcnt[i][fromc]++; colsum[i][fromc] += w.cost;
			vcole[i][fromc].push_back(w);
			w.cc = fromc;
		}
	}

	dst.resize(vnum + 1, 1e18);
	for (int i = n + 1; i < vnum; i++) V.push_back(vector<Line>());

	for (int i = 1; i <= n; i++) {
		for (int w : vc[i]) {
			int col = w, idx = lower_bound(vc[i].begin(), vc[i].end(), col) - vc[i].begin();
			if (colcnt[i][idx] <= 1) continue;
			for (Line& l : vcole[i][idx])
				V[vidx[i][idx]].push_back({ l.to, l.col, colsum[i][idx] - l.cost, idx });
		}
	}
	for (int i = 1; i <= n; i++) {
		int sz = V[i].size();
		for (int j = 0; j < sz; j++) {
			Line& w = V[i][j];
			int idx = lower_bound(vc[w.to].begin(), vc[w.to].end(), w.col) - vc[w.to].begin();
			if (colcnt[w.to][idx] <= 1) continue;
			V[i].push_back({ vidx[w.to][idx], w.col, 0, idx });
		}
	}

	vector<bool> vit(vnum + 1);

	priority_queue<Q> pq;
	pq.push({ 1, 0 }); dst[1] = 0;

	ll cnt = 0;

	while (!pq.empty()) {
		Q top = pq.top(); pq.pop();

		if (top.pos == n) break;
		if (vit[top.pos]) continue;
		vit[top.pos] = true;

		for (Line& w : V[top.pos]) {
			ll& ret = dst[w.to];
			if (top.pos <= n) {
				if (w.to > n) {
					if (ret > top.cost) {
						ret = top.cost;
						pq.push({ w.to, ret });
					}
				}
				else {
					int idx = w.cc;
					if (colcnt[top.pos][idx] == 1) {
						if (ret > top.cost) {
							ret = top.cost;
							pq.push({ w.to, ret });
						}
					}
					else {
						if (ret > top.cost + w.cost) {
							ret = top.cost + w.cost;
							pq.push({ w.to, ret });
						}
						if (ret > top.cost + colsum[top.pos][idx] - w.cost) {
							ret = top.cost + colsum[top.pos][idx] - w.cost;
							pq.push({ w.to, ret });
						}
					}
				}
			}
			else {
				if (ret > top.cost + w.cost) {
					ret = top.cost + w.cost;
					pq.push({ w.to, ret });
				}
			}
		}
	}

	cout << (dst[n] == 1e18 ? -1 : dst[n]) << "\n";

	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:92:5: warning: unused variable 'cnt' [-Wunused-variable]
   92 |  ll cnt = 0;
      |     ^~~

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 2 ms 316 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 584 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 6 ms 1228 KB Output is correct
10 Correct 4 ms 1228 KB Output is correct
11 Correct 3 ms 1228 KB Output is correct
12 Correct 3 ms 1092 KB Output is correct
13 Correct 6 ms 1228 KB Output is correct
14 Correct 3 ms 1216 KB Output is correct
15 Correct 3 ms 972 KB Output is correct
16 Correct 4 ms 1228 KB Output is correct
17 Correct 4 ms 1016 KB Output is correct
18 Correct 2 ms 716 KB Output is correct
19 Correct 3 ms 972 KB Output is correct
20 Correct 3 ms 1092 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 33784 KB Output is correct
2 Correct 95 ms 15940 KB Output is correct
3 Correct 234 ms 47884 KB Output is correct
4 Correct 135 ms 24628 KB Output is correct
5 Correct 755 ms 93588 KB Output is correct
6 Correct 638 ms 90176 KB Output is correct
7 Correct 525 ms 86620 KB Output is correct
8 Correct 819 ms 89908 KB Output is correct
9 Correct 674 ms 89880 KB Output is correct
10 Correct 399 ms 54328 KB Output is correct
11 Correct 265 ms 53596 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 2 ms 316 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 584 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 6 ms 1228 KB Output is correct
10 Correct 4 ms 1228 KB Output is correct
11 Correct 3 ms 1228 KB Output is correct
12 Correct 3 ms 1092 KB Output is correct
13 Correct 6 ms 1228 KB Output is correct
14 Correct 3 ms 1216 KB Output is correct
15 Correct 3 ms 972 KB Output is correct
16 Correct 4 ms 1228 KB Output is correct
17 Correct 4 ms 1016 KB Output is correct
18 Correct 2 ms 716 KB Output is correct
19 Correct 3 ms 972 KB Output is correct
20 Correct 3 ms 1092 KB Output is correct
21 Correct 214 ms 33784 KB Output is correct
22 Correct 95 ms 15940 KB Output is correct
23 Correct 234 ms 47884 KB Output is correct
24 Correct 135 ms 24628 KB Output is correct
25 Correct 755 ms 93588 KB Output is correct
26 Correct 638 ms 90176 KB Output is correct
27 Correct 525 ms 86620 KB Output is correct
28 Correct 819 ms 89908 KB Output is correct
29 Correct 674 ms 89880 KB Output is correct
30 Correct 399 ms 54328 KB Output is correct
31 Correct 265 ms 53596 KB Output is correct
32 Correct 158 ms 46072 KB Output is correct
33 Correct 204 ms 45900 KB Output is correct
34 Correct 413 ms 63780 KB Output is correct
35 Correct 292 ms 55448 KB Output is correct
36 Correct 456 ms 69424 KB Output is correct
37 Correct 443 ms 79944 KB Output is correct
38 Correct 431 ms 95220 KB Output is correct
39 Correct 223 ms 63572 KB Output is correct
40 Correct 766 ms 95248 KB Output is correct
41 Correct 741 ms 95576 KB Output is correct
42 Correct 614 ms 89368 KB Output is correct
43 Correct 255 ms 40836 KB Output is correct
44 Correct 307 ms 74848 KB Output is correct
45 Correct 514 ms 78424 KB Output is correct
46 Correct 442 ms 76916 KB Output is correct
47 Correct 455 ms 76504 KB Output is correct
48 Correct 621 ms 99044 KB Output is correct