oj.uz

Submission #522280

# Submission time Handle Problem Language Result Execution time Memory
522280 2022-02-04T13:16:32 Z AdamGS Robot (JOI21_ho_t4) C++17
100 / 100
 2944 ms 134636 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e5+7;
const ll INF=1e18+7;
vector<pair<int,pair<int,int>>>V[LIM];
ll odl[LIM], koszt[2*LIM], kolor[2*LIM];
map<pair<int,int>,int>odw;
map<pair<int,int>,ll>sum, ma1, ma2, ind1, ind2;
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, m;
	cin >> n >> m;
	rep(i, m) {
		int a, b;
		cin >> a >> b >> kolor[i] >> koszt[i]; --a; --b;
		V[a].pb({kolor[i], {i, b}});
		V[b].pb({kolor[i], {i, a}});
		sum[{a, kolor[i]}]+=koszt[i];
		sum[{b, kolor[i]}]+=koszt[i];
		rep(j, 2) {
			if(koszt[i]>=ma1[{a, kolor[i]}]) {
				ma2[{a, kolor[i]}]=ma1[{a, kolor[i]}];
				ind2[{a, kolor[i]}]=ind1[{a, kolor[i]}];
				ma1[{a, kolor[i]}]=koszt[i];
				ind1[{a, kolor[i]}]=i;
			} else if(koszt[i]>=ma2[{a, kolor[i]}]) {
				ma2[{a, kolor[i]}]=koszt[i];
				ind2[{a, kolor[i]}]=i;
			}
			swap(a, b);
		}
	}
	rep(i, n) {
		odl[i]=INF;
		sort(all(V[i]));
	}
	priority_queue<pair<ll,pair<int,int>>>q;
	q.push({0, {0, -1}});
	while(!q.empty()) {
		ll o=-q.top().st, p=q.top().nd.st, lst=q.top().nd.nd; q.pop();
		if(odw[{p, lst}]) continue;
		odw[{p, lst}]=1;
		if(odl[p]==INF) {
			odl[p]=o;
			for(auto i : V[p]) {
				if(!odw[{i.nd.nd, i.nd.st}]) q.push({-o-koszt[i.nd.st], {i.nd.nd, i.nd.st}});
				if(!odw[{i.nd.nd, -1}]) q.push({-o-sum[{p, i.st}]+koszt[i.nd.st], {i.nd.nd, -1}});
			}
		}
		if(lst==-1) continue;
		if(ind1[{p, kolor[lst]}]==lst) {
			if(ma2[{p, kolor[lst]}]) {
				pair<int,pair<int,int>>xd={kolor[lst], {ind2[{p, kolor[lst]}], -1}};
				auto it=lower_bound(all(V[p]), xd);
				int x=it-V[p].begin();
				if(!odw[{V[p][x].nd.nd, -1}]) {
					q.push({-o-sum[{p, kolor[lst]}]+koszt[lst]+ma2[{p, kolor[lst]}], {V[p][x].nd.nd, -1}});
				}
			}
		} else {
			pair<int,pair<int,int>>xd={kolor[lst], {ind1[{p, kolor[lst]}], -1}};
			auto it=lower_bound(all(V[p]), xd);
			int x=it-V[p].begin();
			if(!odw[{V[p][x].nd.nd, -1}]) {
				q.push({-o-sum[{p, kolor[lst]}]+koszt[lst]+ma1[{p, kolor[lst]}], {V[p][x].nd.nd, -1}});
			}
		}
	}
	cout << (odl[n-1]==INF?-1:odl[n-1]) << '\n';
}

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 1 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 4 ms 3020 KB Output is correct
8 Correct 3 ms 2764 KB Output is correct
9 Correct 11 ms 3872 KB Output is correct
10 Correct 10 ms 3708 KB Output is correct
11 Correct 9 ms 3532 KB Output is correct
12 Correct 9 ms 3404 KB Output is correct
13 Correct 8 ms 3404 KB Output is correct
14 Correct 11 ms 3488 KB Output is correct
15 Correct 6 ms 3148 KB Output is correct
16 Correct 10 ms 3428 KB Output is correct
17 Correct 8 ms 3404 KB Output is correct
18 Correct 3 ms 3020 KB Output is correct
19 Correct 9 ms 3276 KB Output is correct
20 Correct 7 ms 3324 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 810 ms 42576 KB Output is correct
2 Correct 348 ms 22348 KB Output is correct
3 Correct 1482 ms 46480 KB Output is correct
4 Correct 510 ms 29236 KB Output is correct
5 Correct 2580 ms 128108 KB Output is correct
6 Correct 2194 ms 115940 KB Output is correct
7 Correct 1454 ms 89420 KB Output is correct
8 Correct 2071 ms 81348 KB Output is correct
9 Correct 2381 ms 81324 KB Output is correct
10 Correct 1185 ms 68016 KB Output is correct
11 Correct 485 ms 34416 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 1 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 4 ms 3020 KB Output is correct
8 Correct 3 ms 2764 KB Output is correct
9 Correct 11 ms 3872 KB Output is correct
10 Correct 10 ms 3708 KB Output is correct
11 Correct 9 ms 3532 KB Output is correct
12 Correct 9 ms 3404 KB Output is correct
13 Correct 8 ms 3404 KB Output is correct
14 Correct 11 ms 3488 KB Output is correct
15 Correct 6 ms 3148 KB Output is correct
16 Correct 10 ms 3428 KB Output is correct
17 Correct 8 ms 3404 KB Output is correct
18 Correct 3 ms 3020 KB Output is correct
19 Correct 9 ms 3276 KB Output is correct
20 Correct 7 ms 3324 KB Output is correct
21 Correct 810 ms 42576 KB Output is correct
22 Correct 348 ms 22348 KB Output is correct
23 Correct 1482 ms 46480 KB Output is correct
24 Correct 510 ms 29236 KB Output is correct
25 Correct 2580 ms 128108 KB Output is correct
26 Correct 2194 ms 115940 KB Output is correct
27 Correct 1454 ms 89420 KB Output is correct
28 Correct 2071 ms 81348 KB Output is correct
29 Correct 2381 ms 81324 KB Output is correct
30 Correct 1185 ms 68016 KB Output is correct
31 Correct 485 ms 34416 KB Output is correct
32 Correct 1862 ms 49176 KB Output is correct
33 Correct 1749 ms 40836 KB Output is correct
34 Correct 2218 ms 74836 KB Output is correct
35 Correct 1793 ms 58764 KB Output is correct
36 Correct 1340 ms 70132 KB Output is correct
37 Correct 1530 ms 77756 KB Output is correct
38 Correct 1390 ms 87728 KB Output is correct
39 Correct 2025 ms 54152 KB Output is correct
40 Correct 2254 ms 82764 KB Output is correct
41 Correct 2604 ms 82968 KB Output is correct
42 Correct 2589 ms 93888 KB Output is correct
43 Correct 913 ms 45804 KB Output is correct
44 Correct 2885 ms 72232 KB Output is correct
45 Correct 1776 ms 72272 KB Output is correct
46 Correct 1465 ms 69392 KB Output is correct
47 Correct 1841 ms 76516 KB Output is correct
48 Correct 2944 ms 134636 KB Output is correct