oj.uz

Submission #850480

# Submission time Handle Problem Language Result Execution time Memory
850480 2023-09-16T16:05:58 Z hqminhuwu Robot (JOI21_ho_t4) C++17
100 / 100
 1016 ms 110064 KB 
#include <bits/stdc++.h>
#define forr(_a,_b,_c) for(_a = _b; _a <= _c; ++_a)
#define ford(_a,_b,_c) for(_a = (_b) + 1; _a --> _c;)
#define forf(_a,_b,_c) for(_a = _b; _a < _c; ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <ll,ll>
#define pll pair <ll,ll>
#define piii pair <ll,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define file "test"
#define ns nd.st
#define nn nd.nd

using namespace std;
const int N = 2e5 + 5;
const ll oo = 1e18;
const ll mod = 1e9 + 7;

map <int,vector<piii>> a[N];
map <int,ll> dp[N],sum[N];
priority_queue <piii,vector<piii>,greater<piii>> q;

void calc(){
	q.push({0,{-1,0}});
	while (!q.empty()){
		piii  u= q.top();
		q.pop();
		u.ns = - u.ns;
		u.nn = -u.nn;
		if (u.st != dp[u.ns][u.nn])
			continue;
		//cout << u.st << " " << u.ns << " " << u.nn << "\n";
		if (!u.nn){
			for (auto &f : a[u.ns])
			for (piii v : f.nd){
				ll cost = u.st + sum[u.ns][v.ns] - v.nn;
				if (dp[v.st][0] > cost)
					dp[v.st][0] = cost, q.push({dp[v.st][0],{-v.st,0}});
				//cout << cost << " ";
				cost = u.st + v.nn;
				//cout << cost << " ";
				if (dp[v.st][0] > cost)
					dp[v.st][0] = cost, q.push({dp[v.st][0],{-v.st,0}});
				cost = u.st;
				//cout << cost << "\n";
				if (!dp[v.st][v.ns] || dp[v.st][v.ns] > cost)
					dp[v.st][v.ns] = cost, q.push({dp[v.st][v.ns],{-v.st,-v.ns}});
			}
		}
		else {
			for (piii v : a[u.ns][u.nn]){
				ll cost = u.st + sum[u.ns][u.nn] - v.nn;
				//cout << cost << "\n";
				if (dp[v.st][0] > cost)
					dp[v.st][0] = cost, q.push({cost,{-v.st,0}});
			}
		}
	}
}

int n,m,i,u,v,w,t;
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	forr (i,1,m){
		cin >> u >> v >> w >> t;
		a[u][w].pb({v,{w,t}});
		a[v][w].pb({u,{w,t}});
		sum[v][w] += t;
		sum[u][w] += t;
	}
	forr (i,2,n)
		dp[i][0] = oo;
	calc();
	if (dp[n][0] == oo)
        cout << "-1";
    else
	cout << dp[n][0];
	return 0;
}
/*



*/

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:83:5: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
   83 |     else
      |     ^~~~
Main.cpp:85:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
   85 |  return 0;
      |  ^~~~~~

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 28640 KB Output is correct
2 Correct 6 ms 28508 KB Output is correct
3 Correct 6 ms 28508 KB Output is correct
4 Correct 6 ms 28508 KB Output is correct
5 Correct 6 ms 28640 KB Output is correct
6 Correct 7 ms 28508 KB Output is correct
7 Correct 7 ms 28844 KB Output is correct
8 Correct 8 ms 28772 KB Output is correct
9 Correct 9 ms 29276 KB Output is correct
10 Correct 9 ms 29232 KB Output is correct
11 Correct 8 ms 29020 KB Output is correct
12 Correct 8 ms 29020 KB Output is correct
13 Correct 8 ms 29020 KB Output is correct
14 Correct 8 ms 29016 KB Output is correct
15 Correct 8 ms 28760 KB Output is correct
16 Correct 8 ms 28908 KB Output is correct
17 Correct 8 ms 29020 KB Output is correct
18 Correct 8 ms 28764 KB Output is correct
19 Correct 8 ms 28764 KB Output is correct
20 Correct 8 ms 29044 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 51752 KB Output is correct
2 Correct 76 ms 40200 KB Output is correct
3 Correct 159 ms 50120 KB Output is correct
4 Correct 89 ms 44412 KB Output is correct
5 Correct 974 ms 108564 KB Output is correct
6 Correct 720 ms 95244 KB Output is correct
7 Correct 336 ms 84392 KB Output is correct
8 Correct 359 ms 73920 KB Output is correct
9 Correct 378 ms 73772 KB Output is correct
10 Correct 298 ms 66964 KB Output is correct
11 Correct 116 ms 53000 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 28640 KB Output is correct
2 Correct 6 ms 28508 KB Output is correct
3 Correct 6 ms 28508 KB Output is correct
4 Correct 6 ms 28508 KB Output is correct
5 Correct 6 ms 28640 KB Output is correct
6 Correct 7 ms 28508 KB Output is correct
7 Correct 7 ms 28844 KB Output is correct
8 Correct 8 ms 28772 KB Output is correct
9 Correct 9 ms 29276 KB Output is correct
10 Correct 9 ms 29232 KB Output is correct
11 Correct 8 ms 29020 KB Output is correct
12 Correct 8 ms 29020 KB Output is correct
13 Correct 8 ms 29020 KB Output is correct
14 Correct 8 ms 29016 KB Output is correct
15 Correct 8 ms 28760 KB Output is correct
16 Correct 8 ms 28908 KB Output is correct
17 Correct 8 ms 29020 KB Output is correct
18 Correct 8 ms 28764 KB Output is correct
19 Correct 8 ms 28764 KB Output is correct
20 Correct 8 ms 29044 KB Output is correct
21 Correct 167 ms 51752 KB Output is correct
22 Correct 76 ms 40200 KB Output is correct
23 Correct 159 ms 50120 KB Output is correct
24 Correct 89 ms 44412 KB Output is correct
25 Correct 974 ms 108564 KB Output is correct
26 Correct 720 ms 95244 KB Output is correct
27 Correct 336 ms 84392 KB Output is correct
28 Correct 359 ms 73920 KB Output is correct
29 Correct 378 ms 73772 KB Output is correct
30 Correct 298 ms 66964 KB Output is correct
31 Correct 116 ms 53000 KB Output is correct
32 Correct 99 ms 46520 KB Output is correct
33 Correct 140 ms 48076 KB Output is correct
34 Correct 373 ms 70140 KB Output is correct
35 Correct 296 ms 60844 KB Output is correct
36 Correct 315 ms 69220 KB Output is correct
37 Correct 364 ms 74616 KB Output is correct
38 Correct 329 ms 85292 KB Output is correct
39 Correct 104 ms 51148 KB Output is correct
40 Correct 359 ms 75424 KB Output is correct
41 Correct 373 ms 75408 KB Output is correct
42 Correct 483 ms 83492 KB Output is correct
43 Correct 181 ms 54020 KB Output is correct
44 Correct 307 ms 61896 KB Output is correct
45 Correct 278 ms 69748 KB Output is correct
46 Correct 240 ms 69716 KB Output is correct
47 Correct 325 ms 73384 KB Output is correct
48 Correct 1016 ms 110064 KB Output is correct