oj.uz

Submission #935006

# Submission time Handle Problem Language Result Execution time Memory
935006 2024-02-28T10:51:25 Z BF001 Robot (JOI21_ho_t4) C++17
100 / 100
 974 ms 97812 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define oo 1e18
#define N 100005
#define M 200005
#define fi first
#define se second

typedef pair<int, pair<int, pair<int, int>>> iii;

struct ii
{	
	int v, c, cst;
};



int n, d[N], m, cle[M], u[M], v[M], cl[M], cst[M];
vector<int> adj[N];
map<int, int> sum[N], d2[N];
map<int, vector<int>> adj2[N];

void ditra(){
	for (int i = 1; i <= n; i++){
		d[i] = oo;
	}
	priority_queue<iii, vector<iii>, greater<iii>> q;
	d[1] = 0;
	q.push({0, {1, {0, 0}}});
	while (!q.empty()){
		int du = q.top().fi;
		int uu = q.top().se.fi;
		int typ = q.top().se.se.se;
		int laste = q.top().se.se.fi;
		q.pop();
		if (typ){
			if (d2[uu][typ] != du) continue;
				for (auto x : adj2[uu][typ]){
				int vv = v[x];
				if (vv == uu) vv = u[x];
				int d3 = sum[uu][typ] - cst[x] + du;
				if (d3 < d[vv]){
					d[vv] = d3;
					q.push({d3, {vv, {x, 0}}});
				}
			}
		}
		else {
			if (d[uu] != du) continue;
			for (auto x : adj[uu]){
				int vv = v[x];
				if (vv == uu) vv = u[x];
				int cost = cst[x];
				int clr = cl[x];
				int d1 = du + sum[uu][clr] - cost;
				if (d1 < d[vv]){
					d[vv] = d1;
					q.push({d1, {vv, {x, 0}}});
				}
				int d22 = du + cost;
				if (d22 < d[vv]){
					d[vv] = d22;
					q.push({d22, {vv, {x, 0}}});
				}
				int d3 = du;
				if (d2[vv].count(clr) == 0 || d3 < d2[vv][clr]){
					d2[vv][clr] = d3;
					q.push({d3, {vv, {x, clr}}});
				}
			}
		}
	}
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
        
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
    	//int u, v, c, cst;
    	cin >> u[i] >> v[i] >> cl[i] >> cst[i];
    	adj[u[i]].push_back(i);
    	adj[v[i]].push_back(i);
    	sum[u[i]][cl[i]] += cst[i];
    	sum[v[i]][cl[i]] += cst[i];
    	adj2[u[i]][cl[i]].push_back(i);
    	adj2[v[i]][cl[i]].push_back(i);
    }

    ditra();

    int res = d[n];
    if (res >= oo) cout << -1;
    else cout << res;

}

Compilation message

Main.cpp: In function 'void ditra()':
Main.cpp:36:7: warning: unused variable 'laste' [-Wunused-variable]
   36 |   int laste = q.top().se.se.fi;
      |       ^~~~~

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25180 KB Output is correct
2 Correct 6 ms 25180 KB Output is correct
3 Correct 5 ms 25176 KB Output is correct
4 Correct 5 ms 25180 KB Output is correct
5 Correct 5 ms 25180 KB Output is correct
6 Correct 5 ms 25036 KB Output is correct
7 Correct 6 ms 25436 KB Output is correct
8 Correct 6 ms 25176 KB Output is correct
9 Correct 8 ms 25948 KB Output is correct
10 Correct 8 ms 25796 KB Output is correct
11 Correct 7 ms 25520 KB Output is correct
12 Correct 6 ms 25432 KB Output is correct
13 Correct 6 ms 25692 KB Output is correct
14 Correct 7 ms 25688 KB Output is correct
15 Correct 6 ms 25540 KB Output is correct
16 Correct 7 ms 25612 KB Output is correct
17 Correct 8 ms 25456 KB Output is correct
18 Correct 5 ms 25276 KB Output is correct
19 Correct 6 ms 25436 KB Output is correct
20 Correct 6 ms 25436 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 46464 KB Output is correct
2 Correct 57 ms 35916 KB Output is correct
3 Correct 135 ms 43152 KB Output is correct
4 Correct 89 ms 39368 KB Output is correct
5 Correct 968 ms 95768 KB Output is correct
6 Correct 718 ms 84600 KB Output is correct
7 Correct 307 ms 76332 KB Output is correct
8 Correct 367 ms 62608 KB Output is correct
9 Correct 380 ms 63284 KB Output is correct
10 Correct 289 ms 60604 KB Output is correct
11 Correct 120 ms 44372 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25180 KB Output is correct
2 Correct 6 ms 25180 KB Output is correct
3 Correct 5 ms 25176 KB Output is correct
4 Correct 5 ms 25180 KB Output is correct
5 Correct 5 ms 25180 KB Output is correct
6 Correct 5 ms 25036 KB Output is correct
7 Correct 6 ms 25436 KB Output is correct
8 Correct 6 ms 25176 KB Output is correct
9 Correct 8 ms 25948 KB Output is correct
10 Correct 8 ms 25796 KB Output is correct
11 Correct 7 ms 25520 KB Output is correct
12 Correct 6 ms 25432 KB Output is correct
13 Correct 6 ms 25692 KB Output is correct
14 Correct 7 ms 25688 KB Output is correct
15 Correct 6 ms 25540 KB Output is correct
16 Correct 7 ms 25612 KB Output is correct
17 Correct 8 ms 25456 KB Output is correct
18 Correct 5 ms 25276 KB Output is correct
19 Correct 6 ms 25436 KB Output is correct
20 Correct 6 ms 25436 KB Output is correct
21 Correct 165 ms 46464 KB Output is correct
22 Correct 57 ms 35916 KB Output is correct
23 Correct 135 ms 43152 KB Output is correct
24 Correct 89 ms 39368 KB Output is correct
25 Correct 968 ms 95768 KB Output is correct
26 Correct 718 ms 84600 KB Output is correct
27 Correct 307 ms 76332 KB Output is correct
28 Correct 367 ms 62608 KB Output is correct
29 Correct 380 ms 63284 KB Output is correct
30 Correct 289 ms 60604 KB Output is correct
31 Correct 120 ms 44372 KB Output is correct
32 Correct 102 ms 39204 KB Output is correct
33 Correct 116 ms 43204 KB Output is correct
34 Correct 370 ms 63244 KB Output is correct
35 Correct 246 ms 55564 KB Output is correct
36 Correct 286 ms 58628 KB Output is correct
37 Correct 339 ms 62844 KB Output is correct
38 Correct 309 ms 75668 KB Output is correct
39 Correct 114 ms 43452 KB Output is correct
40 Correct 372 ms 63928 KB Output is correct
41 Correct 395 ms 64336 KB Output is correct
42 Correct 460 ms 75192 KB Output is correct
43 Correct 164 ms 48884 KB Output is correct
44 Correct 301 ms 54540 KB Output is correct
45 Correct 312 ms 59988 KB Output is correct
46 Correct 285 ms 60140 KB Output is correct
47 Correct 304 ms 62248 KB Output is correct
48 Correct 974 ms 97812 KB Output is correct