# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
659034 |
2022-11-16T02:00:58 Z |
rsjw |
Robot (JOI21_ho_t4) |
C++17 |
|
963 ms |
120048 KB |
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
const int N = 500010;
#define int long long
namespace SSSP {
struct edge {
int to,w;
edge *nex;
}*head[N];
void add(int u,int v,int w) {
// printf("%d ----%d-----> %d\n",u,w,v);
edge *cur=new edge;
cur->to=v;
cur->nex=head[u];
cur->w=w;
head[u]=cur;
}
int vis[N],dis[N];
priority_queue<pair<int,int> > q;
void dij(int s) {
int u;
memset(dis,0x3f,sizeof(dis));
dis[s]=0;
q.push(mp(-dis[s],s));
while(!q.empty()) {
u=q.top().second;
q.pop();
if(vis[u]) continue;
vis[u]=1;
for(edge *cur=head[u]; cur; cur=cur->nex) {
if(dis[cur->to]>dis[u]+cur->w) {
if(vis[cur->to]) printf("weird");
dis[cur->to]=dis[u]+cur->w;
q.push(mp(-dis[cur->to],cur->to));
}
}
}
}
} using namespace SSSP;
int cnt[N];
vector<tuple<int,int,int>> a[N];
int tot;
map<int,int> s[N];
signed main() {
// freopen("1.in","r",stdin);
int n,m,i,u,v,c,w;
cin>>n>>m;
tot=n;
for(i=1; i<=m; i++) {
cin>>u>>v>>c>>w;
a[u].emplace_back(v,c,w);
a[v].emplace_back(u,c,w);
if(!s[u][c]) s[u][c]=++tot;
if(!s[v][c]) s[v][c]=++tot;
}
for(u=1; u<=n; u++) {
for(auto x:a[u]) {
tie(v,c,w) = x;
cnt[c]+=w;
}
for(auto x:a[u]) {
tie(v,c,w) = x;
add(u,v,min(w,cnt[c]-w));
add(u,s[v][c],0);
add(s[u][c],v,cnt[c]-w);
}
for(auto x:a[u]) {
tie(v,c,w) = x;
cnt[c]=0;
}
}
dij(1);
if(dis[n]==0x3f3f3f3f3f3f3f3f) dis[n]=-1;
cout<<dis[n]<<endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
39380 KB |
Output is correct |
2 |
Correct |
22 ms |
39380 KB |
Output is correct |
3 |
Correct |
20 ms |
39376 KB |
Output is correct |
4 |
Correct |
19 ms |
39380 KB |
Output is correct |
5 |
Correct |
19 ms |
39512 KB |
Output is correct |
6 |
Correct |
22 ms |
39424 KB |
Output is correct |
7 |
Correct |
20 ms |
39708 KB |
Output is correct |
8 |
Correct |
19 ms |
39520 KB |
Output is correct |
9 |
Correct |
22 ms |
40172 KB |
Output is correct |
10 |
Correct |
23 ms |
40084 KB |
Output is correct |
11 |
Correct |
23 ms |
40076 KB |
Output is correct |
12 |
Correct |
23 ms |
40020 KB |
Output is correct |
13 |
Correct |
22 ms |
40096 KB |
Output is correct |
14 |
Correct |
24 ms |
40144 KB |
Output is correct |
15 |
Correct |
20 ms |
39776 KB |
Output is correct |
16 |
Correct |
26 ms |
40076 KB |
Output is correct |
17 |
Correct |
29 ms |
39992 KB |
Output is correct |
18 |
Correct |
26 ms |
39640 KB |
Output is correct |
19 |
Correct |
22 ms |
40040 KB |
Output is correct |
20 |
Correct |
25 ms |
39884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
212 ms |
67332 KB |
Output is correct |
2 |
Correct |
96 ms |
52300 KB |
Output is correct |
3 |
Correct |
259 ms |
80384 KB |
Output is correct |
4 |
Correct |
142 ms |
58060 KB |
Output is correct |
5 |
Correct |
863 ms |
118152 KB |
Output is correct |
6 |
Correct |
798 ms |
113744 KB |
Output is correct |
7 |
Correct |
434 ms |
106460 KB |
Output is correct |
8 |
Correct |
539 ms |
103892 KB |
Output is correct |
9 |
Correct |
558 ms |
104040 KB |
Output is correct |
10 |
Correct |
458 ms |
84032 KB |
Output is correct |
11 |
Correct |
239 ms |
72672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
39380 KB |
Output is correct |
2 |
Correct |
22 ms |
39380 KB |
Output is correct |
3 |
Correct |
20 ms |
39376 KB |
Output is correct |
4 |
Correct |
19 ms |
39380 KB |
Output is correct |
5 |
Correct |
19 ms |
39512 KB |
Output is correct |
6 |
Correct |
22 ms |
39424 KB |
Output is correct |
7 |
Correct |
20 ms |
39708 KB |
Output is correct |
8 |
Correct |
19 ms |
39520 KB |
Output is correct |
9 |
Correct |
22 ms |
40172 KB |
Output is correct |
10 |
Correct |
23 ms |
40084 KB |
Output is correct |
11 |
Correct |
23 ms |
40076 KB |
Output is correct |
12 |
Correct |
23 ms |
40020 KB |
Output is correct |
13 |
Correct |
22 ms |
40096 KB |
Output is correct |
14 |
Correct |
24 ms |
40144 KB |
Output is correct |
15 |
Correct |
20 ms |
39776 KB |
Output is correct |
16 |
Correct |
26 ms |
40076 KB |
Output is correct |
17 |
Correct |
29 ms |
39992 KB |
Output is correct |
18 |
Correct |
26 ms |
39640 KB |
Output is correct |
19 |
Correct |
22 ms |
40040 KB |
Output is correct |
20 |
Correct |
25 ms |
39884 KB |
Output is correct |
21 |
Correct |
212 ms |
67332 KB |
Output is correct |
22 |
Correct |
96 ms |
52300 KB |
Output is correct |
23 |
Correct |
259 ms |
80384 KB |
Output is correct |
24 |
Correct |
142 ms |
58060 KB |
Output is correct |
25 |
Correct |
863 ms |
118152 KB |
Output is correct |
26 |
Correct |
798 ms |
113744 KB |
Output is correct |
27 |
Correct |
434 ms |
106460 KB |
Output is correct |
28 |
Correct |
539 ms |
103892 KB |
Output is correct |
29 |
Correct |
558 ms |
104040 KB |
Output is correct |
30 |
Correct |
458 ms |
84032 KB |
Output is correct |
31 |
Correct |
239 ms |
72672 KB |
Output is correct |
32 |
Correct |
290 ms |
80912 KB |
Output is correct |
33 |
Correct |
277 ms |
75212 KB |
Output is correct |
34 |
Correct |
492 ms |
90132 KB |
Output is correct |
35 |
Correct |
349 ms |
80680 KB |
Output is correct |
36 |
Correct |
363 ms |
84056 KB |
Output is correct |
37 |
Correct |
411 ms |
96428 KB |
Output is correct |
38 |
Correct |
464 ms |
110600 KB |
Output is correct |
39 |
Correct |
298 ms |
92484 KB |
Output is correct |
40 |
Correct |
594 ms |
105200 KB |
Output is correct |
41 |
Correct |
689 ms |
105536 KB |
Output is correct |
42 |
Correct |
751 ms |
105044 KB |
Output is correct |
43 |
Correct |
261 ms |
73416 KB |
Output is correct |
44 |
Correct |
490 ms |
102336 KB |
Output is correct |
45 |
Correct |
463 ms |
90956 KB |
Output is correct |
46 |
Correct |
424 ms |
86980 KB |
Output is correct |
47 |
Correct |
426 ms |
91636 KB |
Output is correct |
48 |
Correct |
963 ms |
120048 KB |
Output is correct |