# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
445606 |
2021-07-19T02:21:20 Z |
jamezzz |
Robot (JOI21_ho_t4) |
C++17 |
|
1014 ms |
54940 KB |
#include <bits/stdc++.h>
using namespace std;
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb emplace_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, int> li;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
mt19937 rng(time(0));
int n,m,a,b,c,d,cnt;
ll tot[500005],dist[500005];
map<ii,int> mp;
vector<iii> AL[500005];
priority_queue<li,vector<li>,greater<li>> pq;
void add(int a,int b,int c,int d){
if(!mp.count({a,c})){
AL[a].push_back({cnt,0,0});
mp[{a,c}]=cnt++;
}
int z=mp[{a,c}];
AL[z].push_back({b,c,d});
tot[z]+=d;
}
void up(int v,ll d){
if(dist[v]<=d)return;
dist[v]=d;
pq.push({dist[v],v});
}
int main(){
sf("%d%d",&n,&m);
cnt=n;
for(int i=0;i<m;++i){
sf("%d%d%d%d",&a,&b,&c,&d);
--a;--b;
add(a,b,c,d);
add(b,a,c,d);
}
for(int i=0;i<cnt;++i)dist[i]=LINF;
dist[0]=0;
pq.push({dist[0],0});
while(!pq.empty()){
ll d;int u;tie(d,u)=pq.top();pq.pop();
if(d>dist[u])continue;
if(u<n){
for(iii t:AL[u]){
int v,c,w;tie(v,c,w)=t;
for(iii t2:AL[v]){
int v2,c2,w2;tie(v2,c2,w2)=t2;
up(v2,d+min((ll)w2,tot[v]-w2));
up(mp[{v2,c2}],d);
}
}
}
else{
for(iii t:AL[u]){
int v,c,w;tie(v,c,w)=t;
up(v,d+tot[u]-w);
}
}
}
if(dist[n-1]==LINF)dist[n-1]=-1;
pf("%lld\n",dist[n-1]);
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:48:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
48 | sf("%d%d",&n,&m);
| ^
Main.cpp:51:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
51 | sf("%d%d%d%d",&a,&b,&c,&d);
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
11980 KB |
Output is correct |
2 |
Correct |
6 ms |
11980 KB |
Output is correct |
3 |
Correct |
6 ms |
11980 KB |
Output is correct |
4 |
Correct |
6 ms |
11980 KB |
Output is correct |
5 |
Correct |
7 ms |
11980 KB |
Output is correct |
6 |
Correct |
7 ms |
11984 KB |
Output is correct |
7 |
Correct |
8 ms |
12080 KB |
Output is correct |
8 |
Correct |
7 ms |
11980 KB |
Output is correct |
9 |
Correct |
10 ms |
12440 KB |
Output is correct |
10 |
Correct |
10 ms |
12384 KB |
Output is correct |
11 |
Correct |
9 ms |
12236 KB |
Output is correct |
12 |
Correct |
8 ms |
12236 KB |
Output is correct |
13 |
Correct |
9 ms |
12236 KB |
Output is correct |
14 |
Correct |
9 ms |
12336 KB |
Output is correct |
15 |
Correct |
8 ms |
12108 KB |
Output is correct |
16 |
Correct |
10 ms |
12236 KB |
Output is correct |
17 |
Correct |
9 ms |
12176 KB |
Output is correct |
18 |
Correct |
8 ms |
12168 KB |
Output is correct |
19 |
Correct |
9 ms |
12108 KB |
Output is correct |
20 |
Correct |
8 ms |
12236 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
282 ms |
23360 KB |
Output is correct |
2 |
Correct |
101 ms |
17764 KB |
Output is correct |
3 |
Correct |
297 ms |
22464 KB |
Output is correct |
4 |
Correct |
153 ms |
19688 KB |
Output is correct |
5 |
Correct |
996 ms |
49712 KB |
Output is correct |
6 |
Correct |
823 ms |
44492 KB |
Output is correct |
7 |
Correct |
512 ms |
34516 KB |
Output is correct |
8 |
Correct |
674 ms |
32212 KB |
Output is correct |
9 |
Correct |
682 ms |
32324 KB |
Output is correct |
10 |
Correct |
490 ms |
31956 KB |
Output is correct |
11 |
Correct |
218 ms |
24644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
11980 KB |
Output is correct |
2 |
Correct |
6 ms |
11980 KB |
Output is correct |
3 |
Correct |
6 ms |
11980 KB |
Output is correct |
4 |
Correct |
6 ms |
11980 KB |
Output is correct |
5 |
Correct |
7 ms |
11980 KB |
Output is correct |
6 |
Correct |
7 ms |
11984 KB |
Output is correct |
7 |
Correct |
8 ms |
12080 KB |
Output is correct |
8 |
Correct |
7 ms |
11980 KB |
Output is correct |
9 |
Correct |
10 ms |
12440 KB |
Output is correct |
10 |
Correct |
10 ms |
12384 KB |
Output is correct |
11 |
Correct |
9 ms |
12236 KB |
Output is correct |
12 |
Correct |
8 ms |
12236 KB |
Output is correct |
13 |
Correct |
9 ms |
12236 KB |
Output is correct |
14 |
Correct |
9 ms |
12336 KB |
Output is correct |
15 |
Correct |
8 ms |
12108 KB |
Output is correct |
16 |
Correct |
10 ms |
12236 KB |
Output is correct |
17 |
Correct |
9 ms |
12176 KB |
Output is correct |
18 |
Correct |
8 ms |
12168 KB |
Output is correct |
19 |
Correct |
9 ms |
12108 KB |
Output is correct |
20 |
Correct |
8 ms |
12236 KB |
Output is correct |
21 |
Correct |
282 ms |
23360 KB |
Output is correct |
22 |
Correct |
101 ms |
17764 KB |
Output is correct |
23 |
Correct |
297 ms |
22464 KB |
Output is correct |
24 |
Correct |
153 ms |
19688 KB |
Output is correct |
25 |
Correct |
996 ms |
49712 KB |
Output is correct |
26 |
Correct |
823 ms |
44492 KB |
Output is correct |
27 |
Correct |
512 ms |
34516 KB |
Output is correct |
28 |
Correct |
674 ms |
32212 KB |
Output is correct |
29 |
Correct |
682 ms |
32324 KB |
Output is correct |
30 |
Correct |
490 ms |
31956 KB |
Output is correct |
31 |
Correct |
218 ms |
24644 KB |
Output is correct |
32 |
Correct |
246 ms |
19940 KB |
Output is correct |
33 |
Correct |
232 ms |
21636 KB |
Output is correct |
34 |
Correct |
592 ms |
31588 KB |
Output is correct |
35 |
Correct |
426 ms |
26680 KB |
Output is correct |
36 |
Correct |
457 ms |
29768 KB |
Output is correct |
37 |
Correct |
492 ms |
31772 KB |
Output is correct |
38 |
Correct |
549 ms |
38524 KB |
Output is correct |
39 |
Correct |
287 ms |
21912 KB |
Output is correct |
40 |
Correct |
665 ms |
32264 KB |
Output is correct |
41 |
Correct |
731 ms |
32284 KB |
Output is correct |
42 |
Correct |
796 ms |
37452 KB |
Output is correct |
43 |
Correct |
304 ms |
24516 KB |
Output is correct |
44 |
Correct |
550 ms |
27756 KB |
Output is correct |
45 |
Correct |
544 ms |
29824 KB |
Output is correct |
46 |
Correct |
449 ms |
29892 KB |
Output is correct |
47 |
Correct |
497 ms |
30752 KB |
Output is correct |
48 |
Correct |
1014 ms |
54940 KB |
Output is correct |