#include <bits/stdc++.h>
using namespace std;
const int MX=5e5+10;
const int INF=1e9;
vector < pair < int , int > > mas[MX];
vector < pair < int , int > > zap[MX];
vector < int > pol[MX];
int ld[MX],sz[MX];
int ans[MX];
int vid[MX];
void ob(int a,int b,int vg)
{
a=ld[a];
b=ld[b];
if(a==b)
{
return;
}
if(sz[a]<sz[b])
{
swap(a,b);
}
while(!pol[b].empty())
{
int zr=pol[b].back();
pol[b].pop_back();
sz[b]--;
pol[a].push_back(zr);
ld[zr]=a;
sz[a]++;
for(auto [vr,in]:zap[zr])
{
if(ld[zr]==ld[vr])
{
ans[in]=max(ans[in],vg);
}
}
}
}
int main()
{
//cin.tie(0);
//ios_base::sync_with_stdio(0);
int n,m,k,kzp;
cin>>n>>m;
int a,b,w;
for(int i=1;i<=m;i++)
{
cin>>a>>b>>w;
mas[a].push_back({b,w});
mas[b].push_back({a,w});
}
fill(vid+1,vid+1+n,INF);
priority_queue < pair < int , int > , vector < pair < int , int > > , greater < pair < int , int > > > q;
cin>>k;
for(int i=1;i<=k;i++)
{
cin>>a;
vid[a]=0;
q.push({0,a});
}
while(!q.empty())
{
int zar=q.top().second;
q.pop();
for(auto [vr,dr]:mas[zar])
{
if((vid[zar]+dr)<vid[vr])
{
vid[vr]=vid[zar]+dr;
q.push({vid[vr],vr});
}
}
}
vector < pair < int , int > > alv;
for(int i=1;i<=n;i++)
{
alv.push_back({vid[i],i});
ld[i]=i;
sz[i]=1;
pol[i].push_back(i);
}
sort(alv.begin(),alv.end());
reverse(alv.begin(),alv.end());
cin>>kzp;
for(int i=1;i<=kzp;i++)
{
cin>>a>>b;
zap[a].push_back({b,i});
zap[b].push_back({a,i});
}
set < int > vvv;
for(auto [zn,vr]:alv)
{
vvv.insert(vr);
for(auto u:mas[vr])
{
if(vvv.find(u.first)!=vvv.end())
{
ob(vr,u.first,zn);
}
}
}
for(int i=1;i<=kzp;i++)
{
cout<<ans[i]<<"\n";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
41048 KB |
Output is correct |
2 |
Correct |
10 ms |
41308 KB |
Output is correct |
3 |
Correct |
11 ms |
41308 KB |
Output is correct |
4 |
Correct |
10 ms |
41052 KB |
Output is correct |
5 |
Correct |
11 ms |
41304 KB |
Output is correct |
6 |
Correct |
11 ms |
41304 KB |
Output is correct |
7 |
Correct |
10 ms |
41048 KB |
Output is correct |
8 |
Correct |
10 ms |
41048 KB |
Output is correct |
9 |
Correct |
13 ms |
41476 KB |
Output is correct |
10 |
Correct |
12 ms |
41304 KB |
Output is correct |
11 |
Correct |
11 ms |
41308 KB |
Output is correct |
12 |
Correct |
11 ms |
41308 KB |
Output is correct |
13 |
Correct |
11 ms |
41308 KB |
Output is correct |
14 |
Correct |
11 ms |
41272 KB |
Output is correct |
15 |
Correct |
11 ms |
41308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
41048 KB |
Output is correct |
2 |
Correct |
10 ms |
41308 KB |
Output is correct |
3 |
Correct |
11 ms |
41308 KB |
Output is correct |
4 |
Correct |
10 ms |
41052 KB |
Output is correct |
5 |
Correct |
11 ms |
41304 KB |
Output is correct |
6 |
Correct |
11 ms |
41304 KB |
Output is correct |
7 |
Correct |
10 ms |
41048 KB |
Output is correct |
8 |
Correct |
10 ms |
41048 KB |
Output is correct |
9 |
Correct |
13 ms |
41476 KB |
Output is correct |
10 |
Correct |
12 ms |
41304 KB |
Output is correct |
11 |
Correct |
11 ms |
41308 KB |
Output is correct |
12 |
Correct |
11 ms |
41308 KB |
Output is correct |
13 |
Correct |
11 ms |
41308 KB |
Output is correct |
14 |
Correct |
11 ms |
41272 KB |
Output is correct |
15 |
Correct |
11 ms |
41308 KB |
Output is correct |
16 |
Correct |
260 ms |
60792 KB |
Output is correct |
17 |
Correct |
844 ms |
79552 KB |
Output is correct |
18 |
Correct |
64 ms |
44768 KB |
Output is correct |
19 |
Correct |
253 ms |
64848 KB |
Output is correct |
20 |
Correct |
828 ms |
79376 KB |
Output is correct |
21 |
Correct |
426 ms |
67468 KB |
Output is correct |
22 |
Correct |
250 ms |
62388 KB |
Output is correct |
23 |
Correct |
887 ms |
79308 KB |
Output is correct |
24 |
Correct |
810 ms |
79384 KB |
Output is correct |
25 |
Correct |
764 ms |
79424 KB |
Output is correct |
26 |
Correct |
257 ms |
64660 KB |
Output is correct |
27 |
Correct |
250 ms |
64780 KB |
Output is correct |
28 |
Correct |
313 ms |
64660 KB |
Output is correct |
29 |
Correct |
297 ms |
64880 KB |
Output is correct |
30 |
Correct |
291 ms |
64780 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
41052 KB |
Output is correct |
2 |
Correct |
11 ms |
41060 KB |
Output is correct |
3 |
Correct |
10 ms |
41256 KB |
Output is correct |
4 |
Correct |
10 ms |
41052 KB |
Output is correct |
5 |
Correct |
12 ms |
41288 KB |
Output is correct |
6 |
Correct |
10 ms |
41052 KB |
Output is correct |
7 |
Correct |
10 ms |
41052 KB |
Output is correct |
8 |
Correct |
11 ms |
41304 KB |
Output is correct |
9 |
Correct |
11 ms |
41052 KB |
Output is correct |
10 |
Correct |
10 ms |
41216 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
334 ms |
61968 KB |
Output is correct |
2 |
Correct |
773 ms |
74172 KB |
Output is correct |
3 |
Correct |
742 ms |
74172 KB |
Output is correct |
4 |
Correct |
184 ms |
57608 KB |
Output is correct |
5 |
Correct |
726 ms |
74172 KB |
Output is correct |
6 |
Correct |
691 ms |
74184 KB |
Output is correct |
7 |
Correct |
707 ms |
74504 KB |
Output is correct |
8 |
Correct |
676 ms |
74028 KB |
Output is correct |
9 |
Correct |
750 ms |
74104 KB |
Output is correct |
10 |
Correct |
660 ms |
74084 KB |
Output is correct |
11 |
Correct |
727 ms |
74008 KB |
Output is correct |
12 |
Correct |
660 ms |
74256 KB |
Output is correct |
13 |
Correct |
762 ms |
74156 KB |
Output is correct |
14 |
Correct |
685 ms |
74184 KB |
Output is correct |
15 |
Correct |
708 ms |
74176 KB |
Output is correct |
16 |
Correct |
723 ms |
74384 KB |
Output is correct |
17 |
Correct |
708 ms |
74040 KB |
Output is correct |
18 |
Correct |
688 ms |
74156 KB |
Output is correct |
19 |
Correct |
159 ms |
57032 KB |
Output is correct |
20 |
Correct |
754 ms |
74216 KB |
Output is correct |
21 |
Correct |
638 ms |
74496 KB |
Output is correct |
22 |
Correct |
237 ms |
59116 KB |
Output is correct |
23 |
Correct |
195 ms |
59340 KB |
Output is correct |
24 |
Correct |
231 ms |
59208 KB |
Output is correct |
25 |
Correct |
179 ms |
59112 KB |
Output is correct |
26 |
Correct |
224 ms |
60008 KB |
Output is correct |
27 |
Correct |
166 ms |
57572 KB |
Output is correct |
28 |
Correct |
178 ms |
59200 KB |
Output is correct |
29 |
Correct |
161 ms |
57536 KB |
Output is correct |
30 |
Correct |
165 ms |
59084 KB |
Output is correct |
31 |
Correct |
175 ms |
57600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
41048 KB |
Output is correct |
2 |
Correct |
10 ms |
41308 KB |
Output is correct |
3 |
Correct |
11 ms |
41308 KB |
Output is correct |
4 |
Correct |
10 ms |
41052 KB |
Output is correct |
5 |
Correct |
11 ms |
41304 KB |
Output is correct |
6 |
Correct |
11 ms |
41304 KB |
Output is correct |
7 |
Correct |
10 ms |
41048 KB |
Output is correct |
8 |
Correct |
10 ms |
41048 KB |
Output is correct |
9 |
Correct |
13 ms |
41476 KB |
Output is correct |
10 |
Correct |
12 ms |
41304 KB |
Output is correct |
11 |
Correct |
11 ms |
41308 KB |
Output is correct |
12 |
Correct |
11 ms |
41308 KB |
Output is correct |
13 |
Correct |
11 ms |
41308 KB |
Output is correct |
14 |
Correct |
11 ms |
41272 KB |
Output is correct |
15 |
Correct |
11 ms |
41308 KB |
Output is correct |
16 |
Correct |
260 ms |
60792 KB |
Output is correct |
17 |
Correct |
844 ms |
79552 KB |
Output is correct |
18 |
Correct |
64 ms |
44768 KB |
Output is correct |
19 |
Correct |
253 ms |
64848 KB |
Output is correct |
20 |
Correct |
828 ms |
79376 KB |
Output is correct |
21 |
Correct |
426 ms |
67468 KB |
Output is correct |
22 |
Correct |
250 ms |
62388 KB |
Output is correct |
23 |
Correct |
887 ms |
79308 KB |
Output is correct |
24 |
Correct |
810 ms |
79384 KB |
Output is correct |
25 |
Correct |
764 ms |
79424 KB |
Output is correct |
26 |
Correct |
257 ms |
64660 KB |
Output is correct |
27 |
Correct |
250 ms |
64780 KB |
Output is correct |
28 |
Correct |
313 ms |
64660 KB |
Output is correct |
29 |
Correct |
297 ms |
64880 KB |
Output is correct |
30 |
Correct |
291 ms |
64780 KB |
Output is correct |
31 |
Correct |
10 ms |
41052 KB |
Output is correct |
32 |
Correct |
11 ms |
41060 KB |
Output is correct |
33 |
Correct |
10 ms |
41256 KB |
Output is correct |
34 |
Correct |
10 ms |
41052 KB |
Output is correct |
35 |
Correct |
12 ms |
41288 KB |
Output is correct |
36 |
Correct |
10 ms |
41052 KB |
Output is correct |
37 |
Correct |
10 ms |
41052 KB |
Output is correct |
38 |
Correct |
11 ms |
41304 KB |
Output is correct |
39 |
Correct |
11 ms |
41052 KB |
Output is correct |
40 |
Correct |
10 ms |
41216 KB |
Output is correct |
41 |
Correct |
334 ms |
61968 KB |
Output is correct |
42 |
Correct |
773 ms |
74172 KB |
Output is correct |
43 |
Correct |
742 ms |
74172 KB |
Output is correct |
44 |
Correct |
184 ms |
57608 KB |
Output is correct |
45 |
Correct |
726 ms |
74172 KB |
Output is correct |
46 |
Correct |
691 ms |
74184 KB |
Output is correct |
47 |
Correct |
707 ms |
74504 KB |
Output is correct |
48 |
Correct |
676 ms |
74028 KB |
Output is correct |
49 |
Correct |
750 ms |
74104 KB |
Output is correct |
50 |
Correct |
660 ms |
74084 KB |
Output is correct |
51 |
Correct |
727 ms |
74008 KB |
Output is correct |
52 |
Correct |
660 ms |
74256 KB |
Output is correct |
53 |
Correct |
762 ms |
74156 KB |
Output is correct |
54 |
Correct |
685 ms |
74184 KB |
Output is correct |
55 |
Correct |
708 ms |
74176 KB |
Output is correct |
56 |
Correct |
723 ms |
74384 KB |
Output is correct |
57 |
Correct |
708 ms |
74040 KB |
Output is correct |
58 |
Correct |
688 ms |
74156 KB |
Output is correct |
59 |
Correct |
159 ms |
57032 KB |
Output is correct |
60 |
Correct |
754 ms |
74216 KB |
Output is correct |
61 |
Correct |
638 ms |
74496 KB |
Output is correct |
62 |
Correct |
237 ms |
59116 KB |
Output is correct |
63 |
Correct |
195 ms |
59340 KB |
Output is correct |
64 |
Correct |
231 ms |
59208 KB |
Output is correct |
65 |
Correct |
179 ms |
59112 KB |
Output is correct |
66 |
Correct |
224 ms |
60008 KB |
Output is correct |
67 |
Correct |
166 ms |
57572 KB |
Output is correct |
68 |
Correct |
178 ms |
59200 KB |
Output is correct |
69 |
Correct |
161 ms |
57536 KB |
Output is correct |
70 |
Correct |
165 ms |
59084 KB |
Output is correct |
71 |
Correct |
175 ms |
57600 KB |
Output is correct |
72 |
Correct |
433 ms |
67272 KB |
Output is correct |
73 |
Correct |
775 ms |
79304 KB |
Output is correct |
74 |
Correct |
776 ms |
79504 KB |
Output is correct |
75 |
Correct |
786 ms |
79276 KB |
Output is correct |
76 |
Correct |
741 ms |
79480 KB |
Output is correct |
77 |
Correct |
736 ms |
79360 KB |
Output is correct |
78 |
Correct |
758 ms |
79328 KB |
Output is correct |
79 |
Correct |
727 ms |
79180 KB |
Output is correct |
80 |
Correct |
759 ms |
79424 KB |
Output is correct |
81 |
Correct |
795 ms |
79160 KB |
Output is correct |
82 |
Correct |
804 ms |
79448 KB |
Output is correct |
83 |
Correct |
772 ms |
79316 KB |
Output is correct |
84 |
Correct |
736 ms |
79228 KB |
Output is correct |
85 |
Correct |
773 ms |
79384 KB |
Output is correct |
86 |
Correct |
763 ms |
79256 KB |
Output is correct |
87 |
Correct |
755 ms |
79376 KB |
Output is correct |
88 |
Correct |
795 ms |
79912 KB |
Output is correct |
89 |
Correct |
264 ms |
62660 KB |
Output is correct |
90 |
Correct |
795 ms |
79296 KB |
Output is correct |
91 |
Correct |
711 ms |
79200 KB |
Output is correct |
92 |
Correct |
304 ms |
64428 KB |
Output is correct |
93 |
Correct |
264 ms |
64604 KB |
Output is correct |
94 |
Correct |
280 ms |
64088 KB |
Output is correct |
95 |
Correct |
259 ms |
64328 KB |
Output is correct |
96 |
Correct |
287 ms |
65048 KB |
Output is correct |
97 |
Correct |
225 ms |
62916 KB |
Output is correct |
98 |
Correct |
257 ms |
64096 KB |
Output is correct |
99 |
Correct |
249 ms |
62844 KB |
Output is correct |
100 |
Correct |
293 ms |
64396 KB |
Output is correct |