#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MX=505;
int N,M,Q;
struct DSU {
int par[MX];
int fd(int v) {
return par[v]==v?v:par[v]=fd(par[v]);
}
bool merge(int u, int v) {
u=fd(u),v=fd(v);
if(u==v) return false;
par[u]=v;
return true;
}
void reset() {
for(int i=1;i<=N;i++) par[i]=i;
}
} ds;
set<pair<int,int>> adj[MX];
const int inf=2e9;
array<int,3> bfs(int S, int T) {
queue<int> q;
q.push(S);
vector<array<int,3>> dist(N+1,{-1,-1,-1});
dist[S]={inf,inf,inf};
while(!q.empty()) {
auto v=q.front(); q.pop();
for(auto [u,w]:adj[v]) {
if(dist[u][0]!=-1) continue;
array<int,3> cur={w,min(u,v),max(u,v)};
dist[u]=min(cur,dist[v]);
q.push(u);
}
}
return dist[T];
}
array<int,3> BFS(int S, int T) {
queue<int> q;
q.push(S);
vector<array<int,3>> dist(N+1,{-1,-1,-1});
dist[S]={0,0,0};
while(!q.empty()) {
auto v=q.front(); q.pop();
for(auto [u,w]:adj[v]) {
if(dist[u][0]!=-1) continue;
array<int,3> cur={w,min(u,v),max(u,v)};
dist[u]=max(cur,dist[v]);
q.push(u);
}
}
return dist[T];
}
array<int,3> e[100000+5];
vector<int> PF[100000+5], SF[100000+5];
set<array<int,4>> E;
map<array<int,3>, int> id;
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin>>N>>M;
vector<array<int,3>> edges;
for(int i=0;i<M;i++) {
int u,v,w;
cin>>u>>v>>w;
e[i]={w,u,v};
id[e[i]]=i;
edges.push_back({w,u,v});
}
sort(edges.begin(),edges.end());
int i=0;
for(auto [w,u,v]:edges) {
assert(E.size()<N);
auto [ww,uu,vv]=bfs(u,v);
if(ww!=-1) {
adj[uu].erase({vv,ww});
adj[vv].erase({uu,ww});
E.erase({ww,uu,vv,id[{ww,uu,vv}]});
}
adj[u].insert({v,w});
adj[v].insert({u,w});
E.insert({w,u,v,id[{w,u,v}]});
for(auto [ww,uu,vv,id]:E) {
PF[i].push_back(id);
}
reverse(PF[i].begin(),PF[i].end());
i++;
}
reverse(edges.begin(),edges.end());
E.clear();
for(int i=1;i<=N;i++) adj[i].clear();
i=M-1;
for(auto [w,u,v]:edges) {
assert(E.size()<N);
auto [ww,uu,vv]=BFS(u,v);
if(ww!=-1) {
adj[uu].erase({vv,ww});
adj[vv].erase({uu,ww});
E.erase({ww,uu,vv,id[{ww,uu,vv}]});
}
adj[u].insert({v,w});
adj[v].insert({u,w});
E.insert({w,u,v,id[{w,u,v}]});
for(auto [ww,uu,vv,id]:E) {
SF[i].push_back(id);
}
i--;
}
reverse(edges.begin(),edges.end());
cin>>Q;
int p=-1;
for(int i=0;i<Q;i++) {
int x;
cin>>x;
while(p+1<edges.size() && x>=edges[p+1][0]) {
p++;
}
ds.reset();
ll res=0;
if(p==(int)edges.size()-1) {
// PF back()
for(auto id:PF[p]) {
auto [w,u,v]=e[id];
res+=x-w;
}
} else if(p==-1) {
// SF[0]
for(auto id:SF[0]) {
auto [w,u,v]=e[id];
res+=w-x;
}
} else {
// PF[p], Sf[p+1]
int i=0,j=0; // 2 pointers
while(i<PF[p].size()&&j<SF[p+1].size()) {
int id=PF[p][i];
auto [w,u,v]=e[id];
int ID=SF[p+1][j];
auto [ww,uu,vv]=e[ID];
if(x-w<ww-x) {
if(ds.merge(u,v))
res+=x-w;
i++;
} else {
if(ds.merge(uu,vv))
res+=ww-x;
j++;
}
}
while(i<PF[p].size()) {
int id=PF[p][i];
auto [w,u,v]=e[id];
if(ds.merge(u,v))
res+=x-w;
i++;
}
while(j<SF[p+1].size()) {
int id=SF[p+1][j];
auto [w,u,v]=e[id];
if(ds.merge(u,v))
res+=w-x;
j++;
}
}
cout<<res<<'\n';
}
}
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from reconstruction.cpp:1:
reconstruction.cpp: In function 'int main()':
reconstruction.cpp:99:18: warning: comparison of integer expressions of different signedness: 'std::set<std::array<int, 4> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
99 | assert(E.size()<N);
| ~~~~~~~~^~
reconstruction.cpp:122:18: warning: comparison of integer expressions of different signedness: 'std::set<std::array<int, 4> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
122 | assert(E.size()<N);
| ~~~~~~~~^~
reconstruction.cpp:147:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
147 | while(p+1<edges.size() && x>=edges[p+1][0]) {
| ~~~^~~~~~~~~~~~~
reconstruction.cpp:168:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
168 | while(i<PF[p].size()&&j<SF[p+1].size()) {
| ~^~~~~~~~~~~~~
reconstruction.cpp:168:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
168 | while(i<PF[p].size()&&j<SF[p+1].size()) {
| ~^~~~~~~~~~~~~~~
reconstruction.cpp:184:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
184 | while(i<PF[p].size()) {
| ~^~~~~~~~~~~~~
reconstruction.cpp:192:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
192 | while(j<SF[p+1].size()) {
| ~^~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4956 KB |
Output is correct |
2 |
Correct |
1 ms |
4956 KB |
Output is correct |
3 |
Correct |
2 ms |
5100 KB |
Output is correct |
4 |
Correct |
1 ms |
4956 KB |
Output is correct |
5 |
Correct |
1 ms |
4956 KB |
Output is correct |
6 |
Correct |
1 ms |
4956 KB |
Output is correct |
7 |
Correct |
2 ms |
4956 KB |
Output is correct |
8 |
Correct |
1 ms |
4956 KB |
Output is correct |
9 |
Correct |
2 ms |
4956 KB |
Output is correct |
10 |
Correct |
1 ms |
4956 KB |
Output is correct |
11 |
Correct |
3 ms |
4956 KB |
Output is correct |
12 |
Correct |
1 ms |
4956 KB |
Output is correct |
13 |
Correct |
1 ms |
4956 KB |
Output is correct |
14 |
Correct |
1 ms |
4956 KB |
Output is correct |
15 |
Correct |
1 ms |
4980 KB |
Output is correct |
16 |
Correct |
2 ms |
4956 KB |
Output is correct |
17 |
Correct |
1 ms |
4956 KB |
Output is correct |
18 |
Correct |
1 ms |
4956 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4956 KB |
Output is correct |
2 |
Correct |
1 ms |
4956 KB |
Output is correct |
3 |
Correct |
2 ms |
5100 KB |
Output is correct |
4 |
Correct |
1 ms |
4956 KB |
Output is correct |
5 |
Correct |
1 ms |
4956 KB |
Output is correct |
6 |
Correct |
1 ms |
4956 KB |
Output is correct |
7 |
Correct |
2 ms |
4956 KB |
Output is correct |
8 |
Correct |
1 ms |
4956 KB |
Output is correct |
9 |
Correct |
2 ms |
4956 KB |
Output is correct |
10 |
Correct |
1 ms |
4956 KB |
Output is correct |
11 |
Correct |
3 ms |
4956 KB |
Output is correct |
12 |
Correct |
1 ms |
4956 KB |
Output is correct |
13 |
Correct |
1 ms |
4956 KB |
Output is correct |
14 |
Correct |
1 ms |
4956 KB |
Output is correct |
15 |
Correct |
1 ms |
4980 KB |
Output is correct |
16 |
Correct |
2 ms |
4956 KB |
Output is correct |
17 |
Correct |
1 ms |
4956 KB |
Output is correct |
18 |
Correct |
1 ms |
4956 KB |
Output is correct |
19 |
Correct |
1 ms |
4956 KB |
Output is correct |
20 |
Correct |
4086 ms |
416944 KB |
Output is correct |
21 |
Correct |
2539 ms |
418580 KB |
Output is correct |
22 |
Correct |
3393 ms |
418648 KB |
Output is correct |
23 |
Correct |
3589 ms |
418724 KB |
Output is correct |
24 |
Correct |
3815 ms |
418816 KB |
Output is correct |
25 |
Correct |
3981 ms |
418604 KB |
Output is correct |
26 |
Correct |
4049 ms |
418800 KB |
Output is correct |
27 |
Correct |
3948 ms |
418800 KB |
Output is correct |
28 |
Correct |
4277 ms |
418624 KB |
Output is correct |
29 |
Correct |
3058 ms |
415716 KB |
Output is correct |
30 |
Correct |
4017 ms |
418740 KB |
Output is correct |
31 |
Correct |
3947 ms |
418892 KB |
Output is correct |
32 |
Correct |
4033 ms |
419008 KB |
Output is correct |
33 |
Correct |
3984 ms |
418696 KB |
Output is correct |
34 |
Correct |
2379 ms |
389096 KB |
Output is correct |
35 |
Correct |
3998 ms |
419144 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4956 KB |
Output is correct |
2 |
Correct |
1 ms |
5072 KB |
Output is correct |
3 |
Correct |
1 ms |
4956 KB |
Output is correct |
4 |
Execution timed out |
5087 ms |
420520 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4956 KB |
Output is correct |
2 |
Correct |
1 ms |
4956 KB |
Output is correct |
3 |
Correct |
2 ms |
5100 KB |
Output is correct |
4 |
Correct |
1 ms |
4956 KB |
Output is correct |
5 |
Correct |
1 ms |
4956 KB |
Output is correct |
6 |
Correct |
1 ms |
4956 KB |
Output is correct |
7 |
Correct |
2 ms |
4956 KB |
Output is correct |
8 |
Correct |
1 ms |
4956 KB |
Output is correct |
9 |
Correct |
2 ms |
4956 KB |
Output is correct |
10 |
Correct |
1 ms |
4956 KB |
Output is correct |
11 |
Correct |
3 ms |
4956 KB |
Output is correct |
12 |
Correct |
1 ms |
4956 KB |
Output is correct |
13 |
Correct |
1 ms |
4956 KB |
Output is correct |
14 |
Correct |
1 ms |
4956 KB |
Output is correct |
15 |
Correct |
1 ms |
4980 KB |
Output is correct |
16 |
Correct |
2 ms |
4956 KB |
Output is correct |
17 |
Correct |
1 ms |
4956 KB |
Output is correct |
18 |
Correct |
1 ms |
4956 KB |
Output is correct |
19 |
Correct |
1 ms |
4956 KB |
Output is correct |
20 |
Execution timed out |
5066 ms |
20020 KB |
Time limit exceeded |
21 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4956 KB |
Output is correct |
2 |
Correct |
1 ms |
4956 KB |
Output is correct |
3 |
Correct |
2 ms |
5100 KB |
Output is correct |
4 |
Correct |
1 ms |
4956 KB |
Output is correct |
5 |
Correct |
1 ms |
4956 KB |
Output is correct |
6 |
Correct |
1 ms |
4956 KB |
Output is correct |
7 |
Correct |
2 ms |
4956 KB |
Output is correct |
8 |
Correct |
1 ms |
4956 KB |
Output is correct |
9 |
Correct |
2 ms |
4956 KB |
Output is correct |
10 |
Correct |
1 ms |
4956 KB |
Output is correct |
11 |
Correct |
3 ms |
4956 KB |
Output is correct |
12 |
Correct |
1 ms |
4956 KB |
Output is correct |
13 |
Correct |
1 ms |
4956 KB |
Output is correct |
14 |
Correct |
1 ms |
4956 KB |
Output is correct |
15 |
Correct |
1 ms |
4980 KB |
Output is correct |
16 |
Correct |
2 ms |
4956 KB |
Output is correct |
17 |
Correct |
1 ms |
4956 KB |
Output is correct |
18 |
Correct |
1 ms |
4956 KB |
Output is correct |
19 |
Correct |
1 ms |
4956 KB |
Output is correct |
20 |
Correct |
4086 ms |
416944 KB |
Output is correct |
21 |
Correct |
2539 ms |
418580 KB |
Output is correct |
22 |
Correct |
3393 ms |
418648 KB |
Output is correct |
23 |
Correct |
3589 ms |
418724 KB |
Output is correct |
24 |
Correct |
3815 ms |
418816 KB |
Output is correct |
25 |
Correct |
3981 ms |
418604 KB |
Output is correct |
26 |
Correct |
4049 ms |
418800 KB |
Output is correct |
27 |
Correct |
3948 ms |
418800 KB |
Output is correct |
28 |
Correct |
4277 ms |
418624 KB |
Output is correct |
29 |
Correct |
3058 ms |
415716 KB |
Output is correct |
30 |
Correct |
4017 ms |
418740 KB |
Output is correct |
31 |
Correct |
3947 ms |
418892 KB |
Output is correct |
32 |
Correct |
4033 ms |
419008 KB |
Output is correct |
33 |
Correct |
3984 ms |
418696 KB |
Output is correct |
34 |
Correct |
2379 ms |
389096 KB |
Output is correct |
35 |
Correct |
3998 ms |
419144 KB |
Output is correct |
36 |
Correct |
4620 ms |
419264 KB |
Output is correct |
37 |
Correct |
2961 ms |
419080 KB |
Output is correct |
38 |
Correct |
3909 ms |
418900 KB |
Output is correct |
39 |
Correct |
4157 ms |
419220 KB |
Output is correct |
40 |
Correct |
4406 ms |
419320 KB |
Output is correct |
41 |
Correct |
4593 ms |
419496 KB |
Output is correct |
42 |
Correct |
4592 ms |
419128 KB |
Output is correct |
43 |
Correct |
4550 ms |
419144 KB |
Output is correct |
44 |
Correct |
4508 ms |
419120 KB |
Output is correct |
45 |
Correct |
3283 ms |
416364 KB |
Output is correct |
46 |
Correct |
4858 ms |
419272 KB |
Output is correct |
47 |
Correct |
4738 ms |
419412 KB |
Output is correct |
48 |
Correct |
4590 ms |
419196 KB |
Output is correct |
49 |
Correct |
4659 ms |
419552 KB |
Output is correct |
50 |
Correct |
2483 ms |
389260 KB |
Output is correct |
51 |
Correct |
4176 ms |
419180 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4956 KB |
Output is correct |
2 |
Correct |
1 ms |
4956 KB |
Output is correct |
3 |
Correct |
2 ms |
5100 KB |
Output is correct |
4 |
Correct |
1 ms |
4956 KB |
Output is correct |
5 |
Correct |
1 ms |
4956 KB |
Output is correct |
6 |
Correct |
1 ms |
4956 KB |
Output is correct |
7 |
Correct |
2 ms |
4956 KB |
Output is correct |
8 |
Correct |
1 ms |
4956 KB |
Output is correct |
9 |
Correct |
2 ms |
4956 KB |
Output is correct |
10 |
Correct |
1 ms |
4956 KB |
Output is correct |
11 |
Correct |
3 ms |
4956 KB |
Output is correct |
12 |
Correct |
1 ms |
4956 KB |
Output is correct |
13 |
Correct |
1 ms |
4956 KB |
Output is correct |
14 |
Correct |
1 ms |
4956 KB |
Output is correct |
15 |
Correct |
1 ms |
4980 KB |
Output is correct |
16 |
Correct |
2 ms |
4956 KB |
Output is correct |
17 |
Correct |
1 ms |
4956 KB |
Output is correct |
18 |
Correct |
1 ms |
4956 KB |
Output is correct |
19 |
Correct |
1 ms |
4956 KB |
Output is correct |
20 |
Correct |
4086 ms |
416944 KB |
Output is correct |
21 |
Correct |
2539 ms |
418580 KB |
Output is correct |
22 |
Correct |
3393 ms |
418648 KB |
Output is correct |
23 |
Correct |
3589 ms |
418724 KB |
Output is correct |
24 |
Correct |
3815 ms |
418816 KB |
Output is correct |
25 |
Correct |
3981 ms |
418604 KB |
Output is correct |
26 |
Correct |
4049 ms |
418800 KB |
Output is correct |
27 |
Correct |
3948 ms |
418800 KB |
Output is correct |
28 |
Correct |
4277 ms |
418624 KB |
Output is correct |
29 |
Correct |
3058 ms |
415716 KB |
Output is correct |
30 |
Correct |
4017 ms |
418740 KB |
Output is correct |
31 |
Correct |
3947 ms |
418892 KB |
Output is correct |
32 |
Correct |
4033 ms |
419008 KB |
Output is correct |
33 |
Correct |
3984 ms |
418696 KB |
Output is correct |
34 |
Correct |
2379 ms |
389096 KB |
Output is correct |
35 |
Correct |
3998 ms |
419144 KB |
Output is correct |
36 |
Correct |
1 ms |
4956 KB |
Output is correct |
37 |
Correct |
1 ms |
5072 KB |
Output is correct |
38 |
Correct |
1 ms |
4956 KB |
Output is correct |
39 |
Execution timed out |
5087 ms |
420520 KB |
Time limit exceeded |
40 |
Halted |
0 ms |
0 KB |
- |