# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
168566 | 2019-12-13T18:44:03 Z | GioChkhaidze | Evacuation plan (IZhO18_plan) | C++14 | 679 ms | 27716 KB |
#include <bits/stdc++.h> #define F first #define S second using namespace std; const int N=1e5+5; int n,m,k,q; bool f[N]; int p[N],d[N],tot[N],ANS[N]; priority_queue < pair < int , int > > Q; vector < pair < int , int > > s,v[N],Query[N]; int P(int x) { if (p[x]==x) return x; return p[x]=P(p[x]); } void Uni(int a,int b,int c) { a=P(a),b=P(b); if (Query[a].size()+tot[a]<Query[b].size()+tot[b]) swap(a,b); for (int i=0; i<Query[b].size(); i++) { if (P(Query[b][i].F)==P(a)) ANS[Query[b][i].S]=c; else Query[a].push_back(Query[b][i]); } p[b]=a; tot[a]+=tot[b]; } main () { scanf("%d%d",&n,&m); for (int i=1; i<=m; i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); v[a].push_back({b,c}); v[b].push_back({a,c}); } scanf("%d",&k); for (int i=1; i<=n; i++) d[i]=1e9; for (int i=1; i<=k; i++) { int x; scanf("%d",&x); d[x]=0; } for (int i=1; i<=n; i++) Q.push({-d[i],i}); while (!Q.empty()) { int x=Q.top().S; Q.pop(); if (f[x]) continue ; f[x]=1; for (int i=0; i<v[x].size(); i++) { int to=v[x][i].F,cost=v[x][i].S; if (!f[to] && d[x]+cost<d[to]) { d[to]=d[x]+cost; Q.push({-d[to],to}); } } } for (int i=1; i<=n; i++) s.push_back({d[i],i}); sort(s.begin(),s.end()); reverse(s.begin(),s.end()); scanf("%d",&q); for (int i=1; i<=q; i++) { int a,b; scanf("%d%d",&a,&b); Query[a].push_back({b,i}); Query[b].push_back({a,i}); } for (int i=1; i<=n; i++) p[i]=i,f[i]=0,tot[i]=1; for (int i=0; i<s.size(); i++) { int x=s[i].S,cost=s[i].F; f[x]=1; for (int i=0; i<v[x].size(); i++) { int to=v[x][i].F; if (f[to]) if (P(x)!=P(to)) Uni(x,to,cost); } } for (int i=1; i<=q; i++) printf("%d\n",ANS[i]); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 4984 KB | Output is correct |
2 | Correct | 7 ms | 5112 KB | Output is correct |
3 | Correct | 7 ms | 5112 KB | Output is correct |
4 | Correct | 6 ms | 5112 KB | Output is correct |
5 | Correct | 7 ms | 5112 KB | Output is correct |
6 | Correct | 7 ms | 5112 KB | Output is correct |
7 | Correct | 6 ms | 5116 KB | Output is correct |
8 | Correct | 6 ms | 5112 KB | Output is correct |
9 | Correct | 7 ms | 5112 KB | Output is correct |
10 | Correct | 7 ms | 5096 KB | Output is correct |
11 | Correct | 7 ms | 5240 KB | Output is correct |
12 | Correct | 7 ms | 5112 KB | Output is correct |
13 | Correct | 7 ms | 5112 KB | Output is correct |
14 | Correct | 7 ms | 5240 KB | Output is correct |
15 | Correct | 7 ms | 5108 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 4984 KB | Output is correct |
2 | Correct | 7 ms | 5112 KB | Output is correct |
3 | Correct | 7 ms | 5112 KB | Output is correct |
4 | Correct | 6 ms | 5112 KB | Output is correct |
5 | Correct | 7 ms | 5112 KB | Output is correct |
6 | Correct | 7 ms | 5112 KB | Output is correct |
7 | Correct | 6 ms | 5116 KB | Output is correct |
8 | Correct | 6 ms | 5112 KB | Output is correct |
9 | Correct | 7 ms | 5112 KB | Output is correct |
10 | Correct | 7 ms | 5096 KB | Output is correct |
11 | Correct | 7 ms | 5240 KB | Output is correct |
12 | Correct | 7 ms | 5112 KB | Output is correct |
13 | Correct | 7 ms | 5112 KB | Output is correct |
14 | Correct | 7 ms | 5240 KB | Output is correct |
15 | Correct | 7 ms | 5108 KB | Output is correct |
16 | Correct | 209 ms | 17332 KB | Output is correct |
17 | Correct | 615 ms | 27588 KB | Output is correct |
18 | Correct | 46 ms | 7284 KB | Output is correct |
19 | Correct | 212 ms | 17248 KB | Output is correct |
20 | Correct | 608 ms | 27572 KB | Output is correct |
21 | Correct | 327 ms | 20052 KB | Output is correct |
22 | Correct | 218 ms | 16364 KB | Output is correct |
23 | Correct | 637 ms | 27556 KB | Output is correct |
24 | Correct | 631 ms | 27528 KB | Output is correct |
25 | Correct | 625 ms | 27552 KB | Output is correct |
26 | Correct | 194 ms | 17128 KB | Output is correct |
27 | Correct | 208 ms | 17124 KB | Output is correct |
28 | Correct | 191 ms | 17000 KB | Output is correct |
29 | Correct | 198 ms | 17124 KB | Output is correct |
30 | Correct | 199 ms | 17252 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 4988 KB | Output is correct |
2 | Correct | 6 ms | 5084 KB | Output is correct |
3 | Correct | 6 ms | 4984 KB | Output is correct |
4 | Correct | 6 ms | 5112 KB | Output is correct |
5 | Correct | 6 ms | 4984 KB | Output is correct |
6 | Correct | 6 ms | 4984 KB | Output is correct |
7 | Correct | 6 ms | 4996 KB | Output is correct |
8 | Correct | 6 ms | 4984 KB | Output is correct |
9 | Correct | 6 ms | 4984 KB | Output is correct |
10 | Correct | 6 ms | 5116 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 261 ms | 15872 KB | Output is correct |
2 | Correct | 517 ms | 23852 KB | Output is correct |
3 | Correct | 514 ms | 23984 KB | Output is correct |
4 | Correct | 129 ms | 11112 KB | Output is correct |
5 | Correct | 527 ms | 24016 KB | Output is correct |
6 | Correct | 518 ms | 23956 KB | Output is correct |
7 | Correct | 511 ms | 23960 KB | Output is correct |
8 | Correct | 527 ms | 23964 KB | Output is correct |
9 | Correct | 509 ms | 23912 KB | Output is correct |
10 | Correct | 522 ms | 23912 KB | Output is correct |
11 | Correct | 527 ms | 23880 KB | Output is correct |
12 | Correct | 539 ms | 24072 KB | Output is correct |
13 | Correct | 517 ms | 23904 KB | Output is correct |
14 | Correct | 551 ms | 23844 KB | Output is correct |
15 | Correct | 532 ms | 23852 KB | Output is correct |
16 | Correct | 501 ms | 23968 KB | Output is correct |
17 | Correct | 507 ms | 23972 KB | Output is correct |
18 | Correct | 521 ms | 23952 KB | Output is correct |
19 | Correct | 127 ms | 11120 KB | Output is correct |
20 | Correct | 523 ms | 23944 KB | Output is correct |
21 | Correct | 470 ms | 22124 KB | Output is correct |
22 | Correct | 131 ms | 13540 KB | Output is correct |
23 | Correct | 145 ms | 11596 KB | Output is correct |
24 | Correct | 134 ms | 13724 KB | Output is correct |
25 | Correct | 132 ms | 13664 KB | Output is correct |
26 | Correct | 132 ms | 11704 KB | Output is correct |
27 | Correct | 128 ms | 11120 KB | Output is correct |
28 | Correct | 135 ms | 13540 KB | Output is correct |
29 | Correct | 128 ms | 11148 KB | Output is correct |
30 | Correct | 135 ms | 13548 KB | Output is correct |
31 | Correct | 127 ms | 11112 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 4984 KB | Output is correct |
2 | Correct | 7 ms | 5112 KB | Output is correct |
3 | Correct | 7 ms | 5112 KB | Output is correct |
4 | Correct | 6 ms | 5112 KB | Output is correct |
5 | Correct | 7 ms | 5112 KB | Output is correct |
6 | Correct | 7 ms | 5112 KB | Output is correct |
7 | Correct | 6 ms | 5116 KB | Output is correct |
8 | Correct | 6 ms | 5112 KB | Output is correct |
9 | Correct | 7 ms | 5112 KB | Output is correct |
10 | Correct | 7 ms | 5096 KB | Output is correct |
11 | Correct | 7 ms | 5240 KB | Output is correct |
12 | Correct | 7 ms | 5112 KB | Output is correct |
13 | Correct | 7 ms | 5112 KB | Output is correct |
14 | Correct | 7 ms | 5240 KB | Output is correct |
15 | Correct | 7 ms | 5108 KB | Output is correct |
16 | Correct | 209 ms | 17332 KB | Output is correct |
17 | Correct | 615 ms | 27588 KB | Output is correct |
18 | Correct | 46 ms | 7284 KB | Output is correct |
19 | Correct | 212 ms | 17248 KB | Output is correct |
20 | Correct | 608 ms | 27572 KB | Output is correct |
21 | Correct | 327 ms | 20052 KB | Output is correct |
22 | Correct | 218 ms | 16364 KB | Output is correct |
23 | Correct | 637 ms | 27556 KB | Output is correct |
24 | Correct | 631 ms | 27528 KB | Output is correct |
25 | Correct | 625 ms | 27552 KB | Output is correct |
26 | Correct | 194 ms | 17128 KB | Output is correct |
27 | Correct | 208 ms | 17124 KB | Output is correct |
28 | Correct | 191 ms | 17000 KB | Output is correct |
29 | Correct | 198 ms | 17124 KB | Output is correct |
30 | Correct | 199 ms | 17252 KB | Output is correct |
31 | Correct | 6 ms | 4988 KB | Output is correct |
32 | Correct | 6 ms | 5084 KB | Output is correct |
33 | Correct | 6 ms | 4984 KB | Output is correct |
34 | Correct | 6 ms | 5112 KB | Output is correct |
35 | Correct | 6 ms | 4984 KB | Output is correct |
36 | Correct | 6 ms | 4984 KB | Output is correct |
37 | Correct | 6 ms | 4996 KB | Output is correct |
38 | Correct | 6 ms | 4984 KB | Output is correct |
39 | Correct | 6 ms | 4984 KB | Output is correct |
40 | Correct | 6 ms | 5116 KB | Output is correct |
41 | Correct | 261 ms | 15872 KB | Output is correct |
42 | Correct | 517 ms | 23852 KB | Output is correct |
43 | Correct | 514 ms | 23984 KB | Output is correct |
44 | Correct | 129 ms | 11112 KB | Output is correct |
45 | Correct | 527 ms | 24016 KB | Output is correct |
46 | Correct | 518 ms | 23956 KB | Output is correct |
47 | Correct | 511 ms | 23960 KB | Output is correct |
48 | Correct | 527 ms | 23964 KB | Output is correct |
49 | Correct | 509 ms | 23912 KB | Output is correct |
50 | Correct | 522 ms | 23912 KB | Output is correct |
51 | Correct | 527 ms | 23880 KB | Output is correct |
52 | Correct | 539 ms | 24072 KB | Output is correct |
53 | Correct | 517 ms | 23904 KB | Output is correct |
54 | Correct | 551 ms | 23844 KB | Output is correct |
55 | Correct | 532 ms | 23852 KB | Output is correct |
56 | Correct | 501 ms | 23968 KB | Output is correct |
57 | Correct | 507 ms | 23972 KB | Output is correct |
58 | Correct | 521 ms | 23952 KB | Output is correct |
59 | Correct | 127 ms | 11120 KB | Output is correct |
60 | Correct | 523 ms | 23944 KB | Output is correct |
61 | Correct | 470 ms | 22124 KB | Output is correct |
62 | Correct | 131 ms | 13540 KB | Output is correct |
63 | Correct | 145 ms | 11596 KB | Output is correct |
64 | Correct | 134 ms | 13724 KB | Output is correct |
65 | Correct | 132 ms | 13664 KB | Output is correct |
66 | Correct | 132 ms | 11704 KB | Output is correct |
67 | Correct | 128 ms | 11120 KB | Output is correct |
68 | Correct | 135 ms | 13540 KB | Output is correct |
69 | Correct | 128 ms | 11148 KB | Output is correct |
70 | Correct | 135 ms | 13548 KB | Output is correct |
71 | Correct | 127 ms | 11112 KB | Output is correct |
72 | Correct | 370 ms | 20840 KB | Output is correct |
73 | Correct | 662 ms | 27600 KB | Output is correct |
74 | Correct | 637 ms | 27552 KB | Output is correct |
75 | Correct | 605 ms | 27588 KB | Output is correct |
76 | Correct | 643 ms | 27512 KB | Output is correct |
77 | Correct | 631 ms | 27716 KB | Output is correct |
78 | Correct | 634 ms | 27620 KB | Output is correct |
79 | Correct | 601 ms | 27624 KB | Output is correct |
80 | Correct | 623 ms | 27600 KB | Output is correct |
81 | Correct | 627 ms | 27604 KB | Output is correct |
82 | Correct | 630 ms | 27628 KB | Output is correct |
83 | Correct | 619 ms | 27696 KB | Output is correct |
84 | Correct | 635 ms | 27532 KB | Output is correct |
85 | Correct | 633 ms | 27484 KB | Output is correct |
86 | Correct | 679 ms | 27464 KB | Output is correct |
87 | Correct | 631 ms | 27576 KB | Output is correct |
88 | Correct | 629 ms | 27648 KB | Output is correct |
89 | Correct | 212 ms | 16644 KB | Output is correct |
90 | Correct | 637 ms | 27624 KB | Output is correct |
91 | Correct | 587 ms | 26532 KB | Output is correct |
92 | Correct | 222 ms | 18656 KB | Output is correct |
93 | Correct | 244 ms | 23032 KB | Output is correct |
94 | Correct | 219 ms | 18476 KB | Output is correct |
95 | Correct | 220 ms | 18692 KB | Output is correct |
96 | Correct | 261 ms | 24264 KB | Output is correct |
97 | Correct | 214 ms | 17476 KB | Output is correct |
98 | Correct | 225 ms | 18644 KB | Output is correct |
99 | Correct | 224 ms | 18256 KB | Output is correct |
100 | Correct | 221 ms | 18624 KB | Output is correct |