# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
544699 | 2022-04-02T15:00:41 Z | krit3379 | Evacuation plan (IZhO18_plan) | C++17 | 643 ms | 58868 KB |
#include<bits/stdc++.h> using namespace std; #define N 100005 struct A{ int a,w; bool operator<(const A& o)const{ return w>o.w; } }; struct B{ int a,b,w; bool operator<(const B& o)const{ return w>o.w; } }; int dis[N],p[N],ans[N]; vector<A> g[N]; vector<B> edge; set<int> s[N]; priority_queue<A> q; int fp(int v){return (v==p[v])?v:p[v]=fp(p[v]);} int main(){ int n,m,qq,i,a,b,w; scanf("%d %d",&n,&m); for(i=1;i<=n;i++)dis[i]=2e9,p[i]=i; for(i=1;i<=m;i++){ scanf("%d %d %d",&a,&b,&w); g[a].push_back({b,w}); g[b].push_back({a,w}); } scanf("%d",&m); for(i=1;i<=m;i++){ scanf("%d",&a); q.push({a,0}); dis[a]=0; } scanf("%d",&qq); for(i=1;i<=qq;i++){ scanf("%d %d",&a,&b); s[a].insert(i); s[b].insert(i); } while(!q.empty()){ auto [a,w]=q.top(); q.pop(); if(w>dis[a])continue; for(auto x:g[a]){ if(w+x.w<dis[x.a])q.push({x.a,w+x.w}),dis[x.a]=w+x.w; } } for(i=1;i<=n;i++){ for(auto x:g[i]) edge.push_back({i,x.a,min(dis[i],dis[x.a])}); } sort(edge.begin(),edge.end()); for(auto [a,b,w]:edge){ a=fp(a),b=fp(b); if(a==b)continue; if(s[a].size()>s[b].size())swap(a,b); for(auto x:s[a]){ if(s[b].count(x)){ ans[x]=w; s[b].erase(x); } else s[b].insert(x); } p[a]=p[b]; } for(i=1;i<=qq;i++)printf("%d\n",ans[i]); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 7252 KB | Output is correct |
2 | Correct | 5 ms | 7488 KB | Output is correct |
3 | Correct | 5 ms | 7508 KB | Output is correct |
4 | Correct | 4 ms | 7252 KB | Output is correct |
5 | Correct | 5 ms | 7508 KB | Output is correct |
6 | Correct | 5 ms | 7508 KB | Output is correct |
7 | Correct | 4 ms | 7352 KB | Output is correct |
8 | Correct | 4 ms | 7380 KB | Output is correct |
9 | Correct | 5 ms | 7508 KB | Output is correct |
10 | Correct | 5 ms | 7508 KB | Output is correct |
11 | Correct | 6 ms | 7572 KB | Output is correct |
12 | Correct | 5 ms | 7544 KB | Output is correct |
13 | Correct | 5 ms | 7508 KB | Output is correct |
14 | Correct | 6 ms | 7508 KB | Output is correct |
15 | Correct | 5 ms | 7508 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 7252 KB | Output is correct |
2 | Correct | 5 ms | 7488 KB | Output is correct |
3 | Correct | 5 ms | 7508 KB | Output is correct |
4 | Correct | 4 ms | 7252 KB | Output is correct |
5 | Correct | 5 ms | 7508 KB | Output is correct |
6 | Correct | 5 ms | 7508 KB | Output is correct |
7 | Correct | 4 ms | 7352 KB | Output is correct |
8 | Correct | 4 ms | 7380 KB | Output is correct |
9 | Correct | 5 ms | 7508 KB | Output is correct |
10 | Correct | 5 ms | 7508 KB | Output is correct |
11 | Correct | 6 ms | 7572 KB | Output is correct |
12 | Correct | 5 ms | 7544 KB | Output is correct |
13 | Correct | 5 ms | 7508 KB | Output is correct |
14 | Correct | 6 ms | 7508 KB | Output is correct |
15 | Correct | 5 ms | 7508 KB | Output is correct |
16 | Correct | 238 ms | 27560 KB | Output is correct |
17 | Correct | 605 ms | 55980 KB | Output is correct |
18 | Correct | 41 ms | 12036 KB | Output is correct |
19 | Correct | 195 ms | 29016 KB | Output is correct |
20 | Correct | 589 ms | 56088 KB | Output is correct |
21 | Correct | 329 ms | 37448 KB | Output is correct |
22 | Correct | 164 ms | 27272 KB | Output is correct |
23 | Correct | 582 ms | 56080 KB | Output is correct |
24 | Correct | 592 ms | 55984 KB | Output is correct |
25 | Correct | 574 ms | 56096 KB | Output is correct |
26 | Correct | 197 ms | 28872 KB | Output is correct |
27 | Correct | 211 ms | 28952 KB | Output is correct |
28 | Correct | 198 ms | 28900 KB | Output is correct |
29 | Correct | 193 ms | 28944 KB | Output is correct |
30 | Correct | 190 ms | 28996 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 7344 KB | Output is correct |
2 | Correct | 4 ms | 7352 KB | Output is correct |
3 | Correct | 4 ms | 7352 KB | Output is correct |
4 | Correct | 4 ms | 7380 KB | Output is correct |
5 | Correct | 4 ms | 7252 KB | Output is correct |
6 | Correct | 4 ms | 7380 KB | Output is correct |
7 | Correct | 5 ms | 7380 KB | Output is correct |
8 | Correct | 4 ms | 7380 KB | Output is correct |
9 | Correct | 4 ms | 7348 KB | Output is correct |
10 | Correct | 5 ms | 7380 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 167 ms | 24724 KB | Output is correct |
2 | Correct | 424 ms | 44304 KB | Output is correct |
3 | Correct | 401 ms | 44368 KB | Output is correct |
4 | Correct | 69 ms | 16116 KB | Output is correct |
5 | Correct | 399 ms | 44404 KB | Output is correct |
6 | Correct | 402 ms | 44336 KB | Output is correct |
7 | Correct | 420 ms | 44416 KB | Output is correct |
8 | Correct | 416 ms | 44456 KB | Output is correct |
9 | Correct | 405 ms | 44464 KB | Output is correct |
10 | Correct | 391 ms | 44320 KB | Output is correct |
11 | Correct | 391 ms | 44464 KB | Output is correct |
12 | Correct | 398 ms | 44452 KB | Output is correct |
13 | Correct | 390 ms | 44352 KB | Output is correct |
14 | Correct | 423 ms | 44412 KB | Output is correct |
15 | Correct | 414 ms | 45292 KB | Output is correct |
16 | Correct | 400 ms | 44336 KB | Output is correct |
17 | Correct | 419 ms | 44320 KB | Output is correct |
18 | Correct | 418 ms | 44396 KB | Output is correct |
19 | Correct | 73 ms | 16064 KB | Output is correct |
20 | Correct | 415 ms | 44400 KB | Output is correct |
21 | Correct | 365 ms | 44472 KB | Output is correct |
22 | Correct | 76 ms | 18292 KB | Output is correct |
23 | Correct | 78 ms | 16588 KB | Output is correct |
24 | Correct | 78 ms | 18324 KB | Output is correct |
25 | Correct | 69 ms | 18312 KB | Output is correct |
26 | Correct | 79 ms | 16656 KB | Output is correct |
27 | Correct | 70 ms | 16024 KB | Output is correct |
28 | Correct | 80 ms | 18332 KB | Output is correct |
29 | Correct | 76 ms | 15996 KB | Output is correct |
30 | Correct | 77 ms | 18332 KB | Output is correct |
31 | Correct | 73 ms | 16048 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 7252 KB | Output is correct |
2 | Correct | 5 ms | 7488 KB | Output is correct |
3 | Correct | 5 ms | 7508 KB | Output is correct |
4 | Correct | 4 ms | 7252 KB | Output is correct |
5 | Correct | 5 ms | 7508 KB | Output is correct |
6 | Correct | 5 ms | 7508 KB | Output is correct |
7 | Correct | 4 ms | 7352 KB | Output is correct |
8 | Correct | 4 ms | 7380 KB | Output is correct |
9 | Correct | 5 ms | 7508 KB | Output is correct |
10 | Correct | 5 ms | 7508 KB | Output is correct |
11 | Correct | 6 ms | 7572 KB | Output is correct |
12 | Correct | 5 ms | 7544 KB | Output is correct |
13 | Correct | 5 ms | 7508 KB | Output is correct |
14 | Correct | 6 ms | 7508 KB | Output is correct |
15 | Correct | 5 ms | 7508 KB | Output is correct |
16 | Correct | 238 ms | 27560 KB | Output is correct |
17 | Correct | 605 ms | 55980 KB | Output is correct |
18 | Correct | 41 ms | 12036 KB | Output is correct |
19 | Correct | 195 ms | 29016 KB | Output is correct |
20 | Correct | 589 ms | 56088 KB | Output is correct |
21 | Correct | 329 ms | 37448 KB | Output is correct |
22 | Correct | 164 ms | 27272 KB | Output is correct |
23 | Correct | 582 ms | 56080 KB | Output is correct |
24 | Correct | 592 ms | 55984 KB | Output is correct |
25 | Correct | 574 ms | 56096 KB | Output is correct |
26 | Correct | 197 ms | 28872 KB | Output is correct |
27 | Correct | 211 ms | 28952 KB | Output is correct |
28 | Correct | 198 ms | 28900 KB | Output is correct |
29 | Correct | 193 ms | 28944 KB | Output is correct |
30 | Correct | 190 ms | 28996 KB | Output is correct |
31 | Correct | 4 ms | 7344 KB | Output is correct |
32 | Correct | 4 ms | 7352 KB | Output is correct |
33 | Correct | 4 ms | 7352 KB | Output is correct |
34 | Correct | 4 ms | 7380 KB | Output is correct |
35 | Correct | 4 ms | 7252 KB | Output is correct |
36 | Correct | 4 ms | 7380 KB | Output is correct |
37 | Correct | 5 ms | 7380 KB | Output is correct |
38 | Correct | 4 ms | 7380 KB | Output is correct |
39 | Correct | 4 ms | 7348 KB | Output is correct |
40 | Correct | 5 ms | 7380 KB | Output is correct |
41 | Correct | 167 ms | 24724 KB | Output is correct |
42 | Correct | 424 ms | 44304 KB | Output is correct |
43 | Correct | 401 ms | 44368 KB | Output is correct |
44 | Correct | 69 ms | 16116 KB | Output is correct |
45 | Correct | 399 ms | 44404 KB | Output is correct |
46 | Correct | 402 ms | 44336 KB | Output is correct |
47 | Correct | 420 ms | 44416 KB | Output is correct |
48 | Correct | 416 ms | 44456 KB | Output is correct |
49 | Correct | 405 ms | 44464 KB | Output is correct |
50 | Correct | 391 ms | 44320 KB | Output is correct |
51 | Correct | 391 ms | 44464 KB | Output is correct |
52 | Correct | 398 ms | 44452 KB | Output is correct |
53 | Correct | 390 ms | 44352 KB | Output is correct |
54 | Correct | 423 ms | 44412 KB | Output is correct |
55 | Correct | 414 ms | 45292 KB | Output is correct |
56 | Correct | 400 ms | 44336 KB | Output is correct |
57 | Correct | 419 ms | 44320 KB | Output is correct |
58 | Correct | 418 ms | 44396 KB | Output is correct |
59 | Correct | 73 ms | 16064 KB | Output is correct |
60 | Correct | 415 ms | 44400 KB | Output is correct |
61 | Correct | 365 ms | 44472 KB | Output is correct |
62 | Correct | 76 ms | 18292 KB | Output is correct |
63 | Correct | 78 ms | 16588 KB | Output is correct |
64 | Correct | 78 ms | 18324 KB | Output is correct |
65 | Correct | 69 ms | 18312 KB | Output is correct |
66 | Correct | 79 ms | 16656 KB | Output is correct |
67 | Correct | 70 ms | 16024 KB | Output is correct |
68 | Correct | 80 ms | 18332 KB | Output is correct |
69 | Correct | 76 ms | 15996 KB | Output is correct |
70 | Correct | 77 ms | 18332 KB | Output is correct |
71 | Correct | 73 ms | 16048 KB | Output is correct |
72 | Correct | 385 ms | 39648 KB | Output is correct |
73 | Correct | 608 ms | 56988 KB | Output is correct |
74 | Correct | 600 ms | 56928 KB | Output is correct |
75 | Correct | 598 ms | 56760 KB | Output is correct |
76 | Correct | 643 ms | 56852 KB | Output is correct |
77 | Correct | 604 ms | 56812 KB | Output is correct |
78 | Correct | 603 ms | 56736 KB | Output is correct |
79 | Correct | 604 ms | 56936 KB | Output is correct |
80 | Correct | 603 ms | 56732 KB | Output is correct |
81 | Correct | 607 ms | 56808 KB | Output is correct |
82 | Correct | 604 ms | 56968 KB | Output is correct |
83 | Correct | 601 ms | 56968 KB | Output is correct |
84 | Correct | 596 ms | 56660 KB | Output is correct |
85 | Correct | 603 ms | 56796 KB | Output is correct |
86 | Correct | 602 ms | 56764 KB | Output is correct |
87 | Correct | 596 ms | 56792 KB | Output is correct |
88 | Correct | 601 ms | 56728 KB | Output is correct |
89 | Correct | 262 ms | 29400 KB | Output is correct |
90 | Correct | 601 ms | 56988 KB | Output is correct |
91 | Correct | 567 ms | 57360 KB | Output is correct |
92 | Correct | 240 ms | 30452 KB | Output is correct |
93 | Correct | 352 ms | 55692 KB | Output is correct |
94 | Correct | 251 ms | 30400 KB | Output is correct |
95 | Correct | 239 ms | 30420 KB | Output is correct |
96 | Correct | 374 ms | 58868 KB | Output is correct |
97 | Correct | 277 ms | 31544 KB | Output is correct |
98 | Correct | 247 ms | 30424 KB | Output is correct |
99 | Correct | 268 ms | 31436 KB | Output is correct |
100 | Correct | 244 ms | 30608 KB | Output is correct |