# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
476648 |
2021-09-27T23:49:19 Z |
czhang2718 |
Robot (JOI21_ho_t4) |
C++14 |
|
1750 ms |
107224 KB |
#include "bits/stdc++.h"
using namespace std;
typedef pair<int, int> pii;
#define f first
#define s second
template<class T> using pqg=priority_queue<T, vector<T>, greater<T>>;
const int N=100000;
const int M=200000;
int n, m;
map<int, vector<int>> adj[N+1];
int c[M], P[M];
map<pii, pair<int, long long>> dp; //{0/1, min}
map<int, long long> sum[N+1];
pii uv[M];
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for(int i=0; i<m; i++){
int u, v; cin >> u >> v >> c[i] >> P[i];
uv[i]={u, v};
adj[u][c[i]].push_back(i);
adj[v][c[i]].push_back(i);
adj[u][0].push_back(i);
adj[v][0].push_back(i);
sum[u][c[i]]+=P[i];
sum[v][c[i]]+=P[i];
sum[u][0]+=P[i];
sum[v][0]+=P[i];
}
pqg<pair<long long, pii>> pq;
pq.push({0, {1, 0}});
while(!pq.empty()){
pair<long long, pii> p=pq.top(); pq.pop();
if(dp[p.s].f) continue;
dp[p.s]={1, p.f};
int x=p.s.f;
if(adj[x][p.s.s].empty()) continue;
for(int e:adj[x][p.s.s]){
int k=uv[e].f==x?uv[e].s:uv[e].f;
if(p.s.s){
if(!dp[{k, 0}].f) pq.push({sum[x][c[e]]-P[e]+p.f, {k, 0}});
}
else{
if(!dp[{k, 0}].f) pq.push({min(sum[x][c[e]]-P[e], (long long)P[e])+p.f, {k, 0}});
if(!dp[{k, c[e]}].f) pq.push({p.f, {k, c[e]}});
}
}
}
if(dp[{n, 0}].f) cout <<dp[{n, 0}].s;
else cout << -1;
}
// when you recolor you're never tied to one color
// star case just works out since you've reached n before hitting the problem
// dp[i][color] - only transition to same color
// dp[i]
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9676 KB |
Output is correct |
2 |
Correct |
5 ms |
9676 KB |
Output is correct |
3 |
Correct |
6 ms |
9804 KB |
Output is correct |
4 |
Correct |
6 ms |
9672 KB |
Output is correct |
5 |
Correct |
5 ms |
9676 KB |
Output is correct |
6 |
Correct |
6 ms |
9736 KB |
Output is correct |
7 |
Correct |
7 ms |
9844 KB |
Output is correct |
8 |
Correct |
7 ms |
9736 KB |
Output is correct |
9 |
Correct |
13 ms |
10632 KB |
Output is correct |
10 |
Correct |
11 ms |
10444 KB |
Output is correct |
11 |
Correct |
9 ms |
10304 KB |
Output is correct |
12 |
Correct |
9 ms |
10316 KB |
Output is correct |
13 |
Correct |
10 ms |
10308 KB |
Output is correct |
14 |
Correct |
9 ms |
10316 KB |
Output is correct |
15 |
Correct |
9 ms |
10188 KB |
Output is correct |
16 |
Correct |
10 ms |
10308 KB |
Output is correct |
17 |
Correct |
9 ms |
10188 KB |
Output is correct |
18 |
Correct |
7 ms |
9948 KB |
Output is correct |
19 |
Correct |
10 ms |
10104 KB |
Output is correct |
20 |
Correct |
9 ms |
10188 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
503 ms |
36564 KB |
Output is correct |
2 |
Correct |
173 ms |
23864 KB |
Output is correct |
3 |
Correct |
652 ms |
37308 KB |
Output is correct |
4 |
Correct |
300 ms |
29076 KB |
Output is correct |
5 |
Correct |
1647 ms |
107224 KB |
Output is correct |
6 |
Correct |
1482 ms |
90788 KB |
Output is correct |
7 |
Correct |
838 ms |
73544 KB |
Output is correct |
8 |
Correct |
995 ms |
66280 KB |
Output is correct |
9 |
Correct |
1074 ms |
66172 KB |
Output is correct |
10 |
Correct |
678 ms |
55428 KB |
Output is correct |
11 |
Correct |
181 ms |
39392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9676 KB |
Output is correct |
2 |
Correct |
5 ms |
9676 KB |
Output is correct |
3 |
Correct |
6 ms |
9804 KB |
Output is correct |
4 |
Correct |
6 ms |
9672 KB |
Output is correct |
5 |
Correct |
5 ms |
9676 KB |
Output is correct |
6 |
Correct |
6 ms |
9736 KB |
Output is correct |
7 |
Correct |
7 ms |
9844 KB |
Output is correct |
8 |
Correct |
7 ms |
9736 KB |
Output is correct |
9 |
Correct |
13 ms |
10632 KB |
Output is correct |
10 |
Correct |
11 ms |
10444 KB |
Output is correct |
11 |
Correct |
9 ms |
10304 KB |
Output is correct |
12 |
Correct |
9 ms |
10316 KB |
Output is correct |
13 |
Correct |
10 ms |
10308 KB |
Output is correct |
14 |
Correct |
9 ms |
10316 KB |
Output is correct |
15 |
Correct |
9 ms |
10188 KB |
Output is correct |
16 |
Correct |
10 ms |
10308 KB |
Output is correct |
17 |
Correct |
9 ms |
10188 KB |
Output is correct |
18 |
Correct |
7 ms |
9948 KB |
Output is correct |
19 |
Correct |
10 ms |
10104 KB |
Output is correct |
20 |
Correct |
9 ms |
10188 KB |
Output is correct |
21 |
Correct |
503 ms |
36564 KB |
Output is correct |
22 |
Correct |
173 ms |
23864 KB |
Output is correct |
23 |
Correct |
652 ms |
37308 KB |
Output is correct |
24 |
Correct |
300 ms |
29076 KB |
Output is correct |
25 |
Correct |
1647 ms |
107224 KB |
Output is correct |
26 |
Correct |
1482 ms |
90788 KB |
Output is correct |
27 |
Correct |
838 ms |
73544 KB |
Output is correct |
28 |
Correct |
995 ms |
66280 KB |
Output is correct |
29 |
Correct |
1074 ms |
66172 KB |
Output is correct |
30 |
Correct |
678 ms |
55428 KB |
Output is correct |
31 |
Correct |
181 ms |
39392 KB |
Output is correct |
32 |
Correct |
575 ms |
29812 KB |
Output is correct |
33 |
Correct |
575 ms |
35428 KB |
Output is correct |
34 |
Correct |
1036 ms |
56832 KB |
Output is correct |
35 |
Correct |
824 ms |
47588 KB |
Output is correct |
36 |
Correct |
802 ms |
64252 KB |
Output is correct |
37 |
Correct |
917 ms |
71824 KB |
Output is correct |
38 |
Correct |
810 ms |
72108 KB |
Output is correct |
39 |
Correct |
688 ms |
34376 KB |
Output is correct |
40 |
Correct |
907 ms |
67540 KB |
Output is correct |
41 |
Correct |
1063 ms |
67760 KB |
Output is correct |
42 |
Correct |
1194 ms |
76168 KB |
Output is correct |
43 |
Correct |
406 ms |
37616 KB |
Output is correct |
44 |
Correct |
1215 ms |
45176 KB |
Output is correct |
45 |
Correct |
854 ms |
63740 KB |
Output is correct |
46 |
Correct |
632 ms |
62420 KB |
Output is correct |
47 |
Correct |
884 ms |
66932 KB |
Output is correct |
48 |
Correct |
1750 ms |
106148 KB |
Output is correct |