# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
168529 | 2019-12-13T12:37:36 Z | achibasadzishvili | Evacuation plan (IZhO18_plan) | C++17 | 855 ms | 32960 KB |
#include <bits/stdc++.h> #define ll int #define f first #define s second #define pb push_back #define mp make_pair using namespace std; ll k,n,m,qq,d[100005],p[100005],c[100005],ans[100005],las,fix[100005]; ll qu[100005],sz[100005]; vector<ll>vec[100005]; vector<pair<ll,ll> >v[100005],q[100005]; set<pair<ll,ll> >st; inline ll find(ll x){ if(p[x] == x)return x; return p[x] = find(p[x]); } inline void join(ll x,ll y){ x = find(x); y = find(y); if(x == y)return; if(qu[x] < qu[y])swap(x , y); qu[x] += qu[y]; sz[x] += sz[y]; for(int i=0; i<q[y].size(); i++){ if(find(q[y][i].f) == x) ans[q[y][i].s] = min(ans[q[y][i].s] , las); q[x].pb(q[y][i]); } p[y] = x; } int main(){ scanf("%d%d",&n,&m); for(int i=1; i<=m; i++){ int x,y,z; scanf("%d%d%d",&x,&y,&z); v[x].pb(mp(y , z)); v[y].pb(mp(x , z)); } scanf("%d",&k); for(int i=1; i<=n; i++){ d[i] = 1000000000; } for(int i=1; i<=k; i++){ scanf("%d",&c[i]); st.insert(mp(0LL , c[i])); d[c[i]] = 0; } while(st.size()){ ll x = (*st.begin()).s; st.erase(st.begin()); for(int i=0; i<v[x].size(); i++){ ll to = v[x][i].f; if(d[to] > d[x] + v[x][i].s){ if(st.find(mp(d[to] , to)) != st.end())st.erase(st.find(mp(d[to] , to))); d[to] = d[x] + v[x][i].s; st.insert(mp(d[to] , to)); } } } scanf("%d",&qq); for(int i=1; i<=qq; i++){ ans[i] = 1000000000; int x,y; scanf("%d%d",&x,&y); q[x].pb(mp(y , i)); q[y].pb(mp(x , i)); } vector<pair<ll,ll> >g; for(int i=1; i<=n; i++){ g.pb(mp(d[i] , i)); } sort(g.begin() , g.end()); reverse(g.begin() , g.end()); for(int i=1; i<=n; i++){ p[i] = i; qu[i] = (int)q[i].size(); vec[i].pb(i); sz[i] = 1; } for(int i=0; i<g.size(); i++){ las = g[i].f; fix[g[i].s] = 1; for(int j=0; j<v[g[i].s].size(); j++){ ll to = v[g[i].s][j].f; if(fix[to] == 1){ join(g[i].s , to); } } } for(int i=1; i<=qq; i++) printf("%d ",ans[i]); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 7416 KB | Output is correct |
2 | Correct | 9 ms | 7548 KB | Output is correct |
3 | Correct | 9 ms | 7544 KB | Output is correct |
4 | Correct | 11 ms | 7416 KB | Output is correct |
5 | Correct | 9 ms | 7564 KB | Output is correct |
6 | Correct | 12 ms | 7508 KB | Output is correct |
7 | Correct | 8 ms | 7416 KB | Output is correct |
8 | Correct | 9 ms | 7408 KB | Output is correct |
9 | Correct | 10 ms | 7544 KB | Output is correct |
10 | Correct | 9 ms | 7544 KB | Output is correct |
11 | Correct | 9 ms | 7544 KB | Output is correct |
12 | Correct | 9 ms | 7544 KB | Output is correct |
13 | Correct | 10 ms | 7544 KB | Output is correct |
14 | Correct | 9 ms | 7672 KB | Output is correct |
15 | Correct | 9 ms | 7544 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 7416 KB | Output is correct |
2 | Correct | 9 ms | 7548 KB | Output is correct |
3 | Correct | 9 ms | 7544 KB | Output is correct |
4 | Correct | 11 ms | 7416 KB | Output is correct |
5 | Correct | 9 ms | 7564 KB | Output is correct |
6 | Correct | 12 ms | 7508 KB | Output is correct |
7 | Correct | 8 ms | 7416 KB | Output is correct |
8 | Correct | 9 ms | 7408 KB | Output is correct |
9 | Correct | 10 ms | 7544 KB | Output is correct |
10 | Correct | 9 ms | 7544 KB | Output is correct |
11 | Correct | 9 ms | 7544 KB | Output is correct |
12 | Correct | 9 ms | 7544 KB | Output is correct |
13 | Correct | 10 ms | 7544 KB | Output is correct |
14 | Correct | 9 ms | 7672 KB | Output is correct |
15 | Correct | 9 ms | 7544 KB | Output is correct |
16 | Correct | 247 ms | 23068 KB | Output is correct |
17 | Correct | 736 ms | 32692 KB | Output is correct |
18 | Correct | 52 ms | 10024 KB | Output is correct |
19 | Correct | 223 ms | 23788 KB | Output is correct |
20 | Correct | 718 ms | 32648 KB | Output is correct |
21 | Correct | 386 ms | 26568 KB | Output is correct |
22 | Correct | 203 ms | 22512 KB | Output is correct |
23 | Correct | 727 ms | 32624 KB | Output is correct |
24 | Correct | 739 ms | 32728 KB | Output is correct |
25 | Correct | 731 ms | 32788 KB | Output is correct |
26 | Correct | 218 ms | 23532 KB | Output is correct |
27 | Correct | 207 ms | 23528 KB | Output is correct |
28 | Correct | 212 ms | 23484 KB | Output is correct |
29 | Correct | 237 ms | 23580 KB | Output is correct |
30 | Correct | 217 ms | 23732 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 7416 KB | Output is correct |
2 | Correct | 8 ms | 7416 KB | Output is correct |
3 | Correct | 8 ms | 7420 KB | Output is correct |
4 | Correct | 8 ms | 7420 KB | Output is correct |
5 | Correct | 8 ms | 7416 KB | Output is correct |
6 | Correct | 8 ms | 7416 KB | Output is correct |
7 | Correct | 8 ms | 7416 KB | Output is correct |
8 | Correct | 8 ms | 7416 KB | Output is correct |
9 | Correct | 8 ms | 7416 KB | Output is correct |
10 | Correct | 8 ms | 7416 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 297 ms | 19096 KB | Output is correct |
2 | Correct | 682 ms | 25932 KB | Output is correct |
3 | Correct | 662 ms | 25980 KB | Output is correct |
4 | Correct | 115 ms | 16436 KB | Output is correct |
5 | Correct | 656 ms | 25960 KB | Output is correct |
6 | Correct | 650 ms | 25928 KB | Output is correct |
7 | Correct | 649 ms | 25836 KB | Output is correct |
8 | Correct | 688 ms | 25904 KB | Output is correct |
9 | Correct | 608 ms | 25796 KB | Output is correct |
10 | Correct | 623 ms | 25808 KB | Output is correct |
11 | Correct | 645 ms | 25860 KB | Output is correct |
12 | Correct | 633 ms | 25920 KB | Output is correct |
13 | Correct | 654 ms | 25924 KB | Output is correct |
14 | Correct | 652 ms | 25812 KB | Output is correct |
15 | Correct | 658 ms | 26044 KB | Output is correct |
16 | Correct | 647 ms | 25920 KB | Output is correct |
17 | Correct | 662 ms | 26036 KB | Output is correct |
18 | Correct | 627 ms | 25788 KB | Output is correct |
19 | Correct | 113 ms | 16360 KB | Output is correct |
20 | Correct | 635 ms | 26040 KB | Output is correct |
21 | Correct | 542 ms | 26268 KB | Output is correct |
22 | Correct | 142 ms | 17896 KB | Output is correct |
23 | Correct | 122 ms | 16936 KB | Output is correct |
24 | Correct | 140 ms | 17948 KB | Output is correct |
25 | Correct | 139 ms | 17896 KB | Output is correct |
26 | Correct | 134 ms | 16876 KB | Output is correct |
27 | Correct | 103 ms | 16368 KB | Output is correct |
28 | Correct | 138 ms | 17904 KB | Output is correct |
29 | Correct | 108 ms | 16344 KB | Output is correct |
30 | Correct | 143 ms | 18008 KB | Output is correct |
31 | Correct | 109 ms | 16368 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 7416 KB | Output is correct |
2 | Correct | 9 ms | 7548 KB | Output is correct |
3 | Correct | 9 ms | 7544 KB | Output is correct |
4 | Correct | 11 ms | 7416 KB | Output is correct |
5 | Correct | 9 ms | 7564 KB | Output is correct |
6 | Correct | 12 ms | 7508 KB | Output is correct |
7 | Correct | 8 ms | 7416 KB | Output is correct |
8 | Correct | 9 ms | 7408 KB | Output is correct |
9 | Correct | 10 ms | 7544 KB | Output is correct |
10 | Correct | 9 ms | 7544 KB | Output is correct |
11 | Correct | 9 ms | 7544 KB | Output is correct |
12 | Correct | 9 ms | 7544 KB | Output is correct |
13 | Correct | 10 ms | 7544 KB | Output is correct |
14 | Correct | 9 ms | 7672 KB | Output is correct |
15 | Correct | 9 ms | 7544 KB | Output is correct |
16 | Correct | 247 ms | 23068 KB | Output is correct |
17 | Correct | 736 ms | 32692 KB | Output is correct |
18 | Correct | 52 ms | 10024 KB | Output is correct |
19 | Correct | 223 ms | 23788 KB | Output is correct |
20 | Correct | 718 ms | 32648 KB | Output is correct |
21 | Correct | 386 ms | 26568 KB | Output is correct |
22 | Correct | 203 ms | 22512 KB | Output is correct |
23 | Correct | 727 ms | 32624 KB | Output is correct |
24 | Correct | 739 ms | 32728 KB | Output is correct |
25 | Correct | 731 ms | 32788 KB | Output is correct |
26 | Correct | 218 ms | 23532 KB | Output is correct |
27 | Correct | 207 ms | 23528 KB | Output is correct |
28 | Correct | 212 ms | 23484 KB | Output is correct |
29 | Correct | 237 ms | 23580 KB | Output is correct |
30 | Correct | 217 ms | 23732 KB | Output is correct |
31 | Correct | 8 ms | 7416 KB | Output is correct |
32 | Correct | 8 ms | 7416 KB | Output is correct |
33 | Correct | 8 ms | 7420 KB | Output is correct |
34 | Correct | 8 ms | 7420 KB | Output is correct |
35 | Correct | 8 ms | 7416 KB | Output is correct |
36 | Correct | 8 ms | 7416 KB | Output is correct |
37 | Correct | 8 ms | 7416 KB | Output is correct |
38 | Correct | 8 ms | 7416 KB | Output is correct |
39 | Correct | 8 ms | 7416 KB | Output is correct |
40 | Correct | 8 ms | 7416 KB | Output is correct |
41 | Correct | 297 ms | 19096 KB | Output is correct |
42 | Correct | 682 ms | 25932 KB | Output is correct |
43 | Correct | 662 ms | 25980 KB | Output is correct |
44 | Correct | 115 ms | 16436 KB | Output is correct |
45 | Correct | 656 ms | 25960 KB | Output is correct |
46 | Correct | 650 ms | 25928 KB | Output is correct |
47 | Correct | 649 ms | 25836 KB | Output is correct |
48 | Correct | 688 ms | 25904 KB | Output is correct |
49 | Correct | 608 ms | 25796 KB | Output is correct |
50 | Correct | 623 ms | 25808 KB | Output is correct |
51 | Correct | 645 ms | 25860 KB | Output is correct |
52 | Correct | 633 ms | 25920 KB | Output is correct |
53 | Correct | 654 ms | 25924 KB | Output is correct |
54 | Correct | 652 ms | 25812 KB | Output is correct |
55 | Correct | 658 ms | 26044 KB | Output is correct |
56 | Correct | 647 ms | 25920 KB | Output is correct |
57 | Correct | 662 ms | 26036 KB | Output is correct |
58 | Correct | 627 ms | 25788 KB | Output is correct |
59 | Correct | 113 ms | 16360 KB | Output is correct |
60 | Correct | 635 ms | 26040 KB | Output is correct |
61 | Correct | 542 ms | 26268 KB | Output is correct |
62 | Correct | 142 ms | 17896 KB | Output is correct |
63 | Correct | 122 ms | 16936 KB | Output is correct |
64 | Correct | 140 ms | 17948 KB | Output is correct |
65 | Correct | 139 ms | 17896 KB | Output is correct |
66 | Correct | 134 ms | 16876 KB | Output is correct |
67 | Correct | 103 ms | 16368 KB | Output is correct |
68 | Correct | 138 ms | 17904 KB | Output is correct |
69 | Correct | 108 ms | 16344 KB | Output is correct |
70 | Correct | 143 ms | 18008 KB | Output is correct |
71 | Correct | 109 ms | 16368 KB | Output is correct |
72 | Correct | 378 ms | 26536 KB | Output is correct |
73 | Correct | 714 ms | 32708 KB | Output is correct |
74 | Correct | 811 ms | 32736 KB | Output is correct |
75 | Correct | 758 ms | 32880 KB | Output is correct |
76 | Correct | 764 ms | 32960 KB | Output is correct |
77 | Correct | 740 ms | 32728 KB | Output is correct |
78 | Correct | 746 ms | 32740 KB | Output is correct |
79 | Correct | 780 ms | 32880 KB | Output is correct |
80 | Correct | 789 ms | 32696 KB | Output is correct |
81 | Correct | 855 ms | 32760 KB | Output is correct |
82 | Correct | 797 ms | 32728 KB | Output is correct |
83 | Correct | 793 ms | 32740 KB | Output is correct |
84 | Correct | 719 ms | 32692 KB | Output is correct |
85 | Correct | 730 ms | 32884 KB | Output is correct |
86 | Correct | 746 ms | 32876 KB | Output is correct |
87 | Correct | 762 ms | 32652 KB | Output is correct |
88 | Correct | 818 ms | 32752 KB | Output is correct |
89 | Correct | 205 ms | 22756 KB | Output is correct |
90 | Correct | 747 ms | 32740 KB | Output is correct |
91 | Correct | 642 ms | 32956 KB | Output is correct |
92 | Correct | 230 ms | 23144 KB | Output is correct |
93 | Correct | 231 ms | 29056 KB | Output is correct |
94 | Correct | 225 ms | 23240 KB | Output is correct |
95 | Correct | 230 ms | 23092 KB | Output is correct |
96 | Correct | 255 ms | 30828 KB | Output is correct |
97 | Correct | 261 ms | 23712 KB | Output is correct |
98 | Correct | 305 ms | 23084 KB | Output is correct |
99 | Correct | 187 ms | 24164 KB | Output is correct |
100 | Correct | 222 ms | 23116 KB | Output is correct |