oj.uz

Submission #630498

# Submission time Handle Problem Language Result Execution time Memory
630498 2022-08-16T12:30:24 Z QwertyPi Robot (JOI21_ho_t4) C++14
34 / 100
 3000 ms 65788 KB 
#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second
#define int long long
using namespace std;

const int N = 100013, M = 400013;
int a[M], b[M], c[M], p[M];
vector<int> G[N];
int d[M][2];
bool vis[M][2];
unordered_map<int, int> Map[N];
int32_t main(){
	int n, m;
	cin >> n >> m;
	a[0] = 0, b[0] = 1, c[0] = 0, p[0] = 0;
	for(int i = 1; i <= m; i++){
		cin >> a[i] >> b[i] >> c[i] >> p[i];
		G[a[i]].push_back(i);
		
		a[m + i] = b[i], b[m + i] = a[i], c[m + i] = c[i], p[m + i] = p[i];
		G[a[m + i]].push_back(m + i);
	}
	
	priority_queue<pair<int, pii>, vector<pair<int, pii>>, greater<pair<int, pii>>> pq;
	pq.push({0, {0, 0}});
	vis[0][0] = true;
	for(int i = 1; i <= m * 2; i++){
		d[i][0] = d[i][1] = (1LL << 60);
	}
	for(int i = 1; i <= n; i++){
		for(auto j : G[i]){
			Map[i][c[j]] += p[j];
		}
	}
	while(pq.size()){
		pair<int, pii> t = pq.top(); pq.pop();
		int dis = t.fi, eid = t.se.fi, r = t.se.se;
		vis[eid][r] = true;
		if(d[eid][r] < dis) continue;
		int u = a[eid], v = b[eid];
		for(auto i : G[v]){
			if(r){
				int cost_1 = dis + p[i];
				int cost_2 = dis + min(Map[v][c[i]] - p[i] - (c[i] == c[eid] && (eid - i) % m != 0 ? p[eid] : 0), p[i]);
				if(cost_1 < d[i][1]){
					d[i][1] = cost_1;
					pq.push({d[i][1], {i, 1}});
				}
				if(cost_2 < d[i][0]){
					d[i][0] = cost_2;
					pq.push({d[i][0], {i, 0}});
				}
			}else{
				int cost_1 = dis + p[i];
				int cost_2 = dis + min(Map[v][c[i]] - p[i], p[i]);
				if(cost_1 < d[i][1]){
					d[i][1] = cost_1;
					pq.push({d[i][1], {i, 1}});
				}
				if(cost_2 < d[i][0]){
					d[i][0] = cost_2;
					pq.push({d[i][0], {i, 0}});
				}
			}
		}
	}
	int ans = INT64_MAX;
	for(int i = 0; i <= m * 2; i++){
		if(b[i] == n){
			ans = min(ans, d[i][0]);
			ans = min(ans, d[i][1]);
		}
	}
	cout << (ans >= (1LL << 60) ? -1 : ans) << endl;
}

Compilation message

Main.cpp: In function 'int32_t main()':
Main.cpp:42:7: warning: unused variable 'u' [-Wunused-variable]
   42 |   int u = a[eid], v = b[eid];
      |       ^

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8200 KB Output is correct
2 Correct 6 ms 8148 KB Output is correct
3 Correct 6 ms 8148 KB Output is correct
4 Correct 4 ms 8148 KB Output is correct
5 Correct 5 ms 8148 KB Output is correct
6 Correct 4 ms 8148 KB Output is correct
7 Correct 8 ms 8384 KB Output is correct
8 Correct 6 ms 8276 KB Output is correct
9 Correct 64 ms 8868 KB Output is correct
10 Correct 37 ms 8904 KB Output is correct
11 Correct 71 ms 8820 KB Output is correct
12 Correct 18 ms 8660 KB Output is correct
13 Correct 41 ms 8788 KB Output is correct
14 Correct 41 ms 8788 KB Output is correct
15 Correct 6 ms 8356 KB Output is correct
16 Correct 8 ms 8476 KB Output is correct
17 Correct 8 ms 8532 KB Output is correct
18 Correct 7 ms 8276 KB Output is correct
19 Correct 11 ms 8532 KB Output is correct
20 Correct 6 ms 8404 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 29068 KB Output is correct
2 Correct 100 ms 18460 KB Output is correct
3 Correct 690 ms 39912 KB Output is correct
4 Correct 171 ms 22012 KB Output is correct
5 Execution timed out 3056 ms 65788 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8200 KB Output is correct
2 Correct 6 ms 8148 KB Output is correct
3 Correct 6 ms 8148 KB Output is correct
4 Correct 4 ms 8148 KB Output is correct
5 Correct 5 ms 8148 KB Output is correct
6 Correct 4 ms 8148 KB Output is correct
7 Correct 8 ms 8384 KB Output is correct
8 Correct 6 ms 8276 KB Output is correct
9 Correct 64 ms 8868 KB Output is correct
10 Correct 37 ms 8904 KB Output is correct
11 Correct 71 ms 8820 KB Output is correct
12 Correct 18 ms 8660 KB Output is correct
13 Correct 41 ms 8788 KB Output is correct
14 Correct 41 ms 8788 KB Output is correct
15 Correct 6 ms 8356 KB Output is correct
16 Correct 8 ms 8476 KB Output is correct
17 Correct 8 ms 8532 KB Output is correct
18 Correct 7 ms 8276 KB Output is correct
19 Correct 11 ms 8532 KB Output is correct
20 Correct 6 ms 8404 KB Output is correct
21 Correct 294 ms 29068 KB Output is correct
22 Correct 100 ms 18460 KB Output is correct
23 Correct 690 ms 39912 KB Output is correct
24 Correct 171 ms 22012 KB Output is correct
25 Execution timed out 3056 ms 65788 KB Time limit exceeded
26 Halted 0 ms 0 KB -