#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MX=505;
int N,M,Q;
struct DSU {
int par[MX],sz[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;
if(sz[u]>sz[v]) swap(u,v);
par[u]=v;
sz[v]+=sz[u];
return true;
}
void reset() {
for(int i=1;i<=N;i++) par[i]=i,sz[i]=1;
}
} ds;
set<array<int,3>> adj[MX];
const int inf=2e9;
pair<int,int> dist[MX];
pair<int,int> bfs(int S, int T) {
queue<int> q;
q.push(S);
for(int i=1;i<=N;i++) dist[i]={-1,-1};
dist[S]={inf,inf};
while(!q.empty()) {
auto v=q.front(); q.pop();
if(v==T) break;
for(auto [u,w,ii]:adj[v]) {
if(dist[u].first!=-1) continue;
dist[u]=min(make_pair(w,ii),dist[v]);
q.push(u);
}
}
return dist[T];
}
pair<int,int> BFS(int S, int T) {
queue<int> q;
q.push(S);
for(int i=1;i<=N;i++) dist[i]={-1,-1};
dist[S]={0,0};
while(!q.empty()) {
auto v=q.front(); q.pop();
if(v==T) break;
for(auto [u,w,ii]:adj[v]) {
if(dist[u].first!=-1) continue;
dist[u]=max(make_pair(w,ii),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 L[100000+5], R[100000+5];
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin>>N>>M;
vector<array<int,4>> 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,i});
}
sort(edges.begin(),edges.end());
int i=0;
for(auto [w,u,v,ID]:edges) {
auto [ww,ii]=bfs(u,v);
auto [WW,uu,vv]=e[ii];
if(ww!=-1) {
adj[uu].erase({vv,ww,ii});
adj[vv].erase({uu,ww,ii});
E.erase({ww,uu,vv,ii});
}
adj[u].insert({v,w,ID});
adj[v].insert({u,w,ID});
E.insert({w,u,v,ID});
for(auto [ww,uu,vv,id]:E) {
PF[i].push_back(id);
}
reverse(PF[i].begin(),PF[i].end());
if(ww!=-1)
L[ID]=(w+ww),assert(ww<=w);
else
L[ID]=0;
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,ID]:edges) {
auto [ww,ii]=BFS(u,v);
auto [WW,uu,vv]=e[ii];
if(ww!=-1) {
adj[uu].erase({vv,ww,ii});
adj[vv].erase({uu,ww,ii});
E.erase({ww,uu,vv,ii});
}
adj[u].insert({v,w,ID});
adj[v].insert({u,w,ID});
E.insert({w,u,v,ID});
for(auto [ww,uu,vv,id]:E) {
SF[i].push_back(id);
}
if(ww!=-1)
R[ID]=(w+ww),assert(ww>=w);
else
R[ID]=2e9+1;
i--;
}
reverse(edges.begin(),edges.end());
vector<pair<int,int>> add, del;
for(int i=0;i<M;i++) {
add.push_back({L[i],i});
del.push_back({R[i],i});
}
sort(add.begin(),add.end());
sort(del.begin(),del.end());
int pa=-1,pd=-1;
set<int> curEdges;
cin>>Q;
for(int i=0;i<Q;i++) {
ll x;
cin>>x;
while(pa+1<add.size() && add[pa+1].first<=2*x) {
curEdges.insert(add[pa+1].second);
pa++;
}
while(pd+1<del.size() && del[pd+1].first<=2*x) {
curEdges.erase(del[pd+1].second);
pd++;
}
ll res=0;
for(auto y:curEdges) res+=abs(e[y][0]-x);
cout<<res<<'\n';
}
}
Compilation message
reconstruction.cpp: In function 'int main()':
reconstruction.cpp:174:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
174 | while(pa+1<add.size() && add[pa+1].first<=2*x) {
| ~~~~^~~~~~~~~~~
reconstruction.cpp:179:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
179 | while(pd+1<del.size() && del[pd+1].first<=2*x) {
| ~~~~^~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
2 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6488 KB |
Output is correct |
4 |
Correct |
1 ms |
6492 KB |
Output is correct |
5 |
Correct |
1 ms |
6492 KB |
Output is correct |
6 |
Correct |
1 ms |
6492 KB |
Output is correct |
7 |
Correct |
1 ms |
6492 KB |
Output is correct |
8 |
Correct |
1 ms |
6492 KB |
Output is correct |
9 |
Correct |
1 ms |
6492 KB |
Output is correct |
10 |
Correct |
1 ms |
6488 KB |
Output is correct |
11 |
Correct |
1 ms |
6492 KB |
Output is correct |
12 |
Correct |
1 ms |
6492 KB |
Output is correct |
13 |
Correct |
1 ms |
6572 KB |
Output is correct |
14 |
Correct |
1 ms |
6492 KB |
Output is correct |
15 |
Correct |
2 ms |
6612 KB |
Output is correct |
16 |
Correct |
1 ms |
6492 KB |
Output is correct |
17 |
Correct |
1 ms |
6492 KB |
Output is correct |
18 |
Correct |
1 ms |
6492 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
2 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6488 KB |
Output is correct |
4 |
Correct |
1 ms |
6492 KB |
Output is correct |
5 |
Correct |
1 ms |
6492 KB |
Output is correct |
6 |
Correct |
1 ms |
6492 KB |
Output is correct |
7 |
Correct |
1 ms |
6492 KB |
Output is correct |
8 |
Correct |
1 ms |
6492 KB |
Output is correct |
9 |
Correct |
1 ms |
6492 KB |
Output is correct |
10 |
Correct |
1 ms |
6488 KB |
Output is correct |
11 |
Correct |
1 ms |
6492 KB |
Output is correct |
12 |
Correct |
1 ms |
6492 KB |
Output is correct |
13 |
Correct |
1 ms |
6572 KB |
Output is correct |
14 |
Correct |
1 ms |
6492 KB |
Output is correct |
15 |
Correct |
2 ms |
6612 KB |
Output is correct |
16 |
Correct |
1 ms |
6492 KB |
Output is correct |
17 |
Correct |
1 ms |
6492 KB |
Output is correct |
18 |
Correct |
1 ms |
6492 KB |
Output is correct |
19 |
Correct |
1 ms |
6492 KB |
Output is correct |
20 |
Correct |
2779 ms |
421236 KB |
Output is correct |
21 |
Correct |
1264 ms |
421312 KB |
Output is correct |
22 |
Correct |
1281 ms |
420816 KB |
Output is correct |
23 |
Correct |
1383 ms |
421812 KB |
Output is correct |
24 |
Correct |
1718 ms |
421444 KB |
Output is correct |
25 |
Correct |
2621 ms |
421976 KB |
Output is correct |
26 |
Correct |
2633 ms |
421200 KB |
Output is correct |
27 |
Correct |
2662 ms |
420976 KB |
Output is correct |
28 |
Correct |
2749 ms |
421376 KB |
Output is correct |
29 |
Correct |
2376 ms |
419048 KB |
Output is correct |
30 |
Correct |
2577 ms |
421200 KB |
Output is correct |
31 |
Correct |
2612 ms |
421208 KB |
Output is correct |
32 |
Correct |
2602 ms |
422672 KB |
Output is correct |
33 |
Correct |
2627 ms |
421052 KB |
Output is correct |
34 |
Correct |
1930 ms |
391288 KB |
Output is correct |
35 |
Correct |
2602 ms |
422064 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
6492 KB |
Output is correct |
2 |
Correct |
2 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Correct |
3717 ms |
433140 KB |
Output is correct |
5 |
Correct |
3714 ms |
443328 KB |
Output is correct |
6 |
Correct |
3767 ms |
443204 KB |
Output is correct |
7 |
Correct |
3197 ms |
359316 KB |
Output is correct |
8 |
Correct |
4818 ms |
322980 KB |
Output is correct |
9 |
Correct |
2857 ms |
311896 KB |
Output is correct |
10 |
Correct |
4083 ms |
444388 KB |
Output is correct |
11 |
Correct |
4754 ms |
318152 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
2 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6488 KB |
Output is correct |
4 |
Correct |
1 ms |
6492 KB |
Output is correct |
5 |
Correct |
1 ms |
6492 KB |
Output is correct |
6 |
Correct |
1 ms |
6492 KB |
Output is correct |
7 |
Correct |
1 ms |
6492 KB |
Output is correct |
8 |
Correct |
1 ms |
6492 KB |
Output is correct |
9 |
Correct |
1 ms |
6492 KB |
Output is correct |
10 |
Correct |
1 ms |
6488 KB |
Output is correct |
11 |
Correct |
1 ms |
6492 KB |
Output is correct |
12 |
Correct |
1 ms |
6492 KB |
Output is correct |
13 |
Correct |
1 ms |
6572 KB |
Output is correct |
14 |
Correct |
1 ms |
6492 KB |
Output is correct |
15 |
Correct |
2 ms |
6612 KB |
Output is correct |
16 |
Correct |
1 ms |
6492 KB |
Output is correct |
17 |
Correct |
1 ms |
6492 KB |
Output is correct |
18 |
Correct |
1 ms |
6492 KB |
Output is correct |
19 |
Correct |
1 ms |
6488 KB |
Output is correct |
20 |
Correct |
2019 ms |
22396 KB |
Output is correct |
21 |
Correct |
2032 ms |
22344 KB |
Output is correct |
22 |
Correct |
2024 ms |
22608 KB |
Output is correct |
23 |
Correct |
2021 ms |
22568 KB |
Output is correct |
24 |
Correct |
2016 ms |
22636 KB |
Output is correct |
25 |
Correct |
2033 ms |
22516 KB |
Output is correct |
26 |
Correct |
2050 ms |
22312 KB |
Output is correct |
27 |
Correct |
2107 ms |
22648 KB |
Output is correct |
28 |
Correct |
2017 ms |
22540 KB |
Output is correct |
29 |
Correct |
2007 ms |
22456 KB |
Output is correct |
30 |
Correct |
2305 ms |
22324 KB |
Output is correct |
31 |
Correct |
2077 ms |
22540 KB |
Output is correct |
32 |
Correct |
2145 ms |
22868 KB |
Output is correct |
33 |
Correct |
2202 ms |
22060 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
2 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6488 KB |
Output is correct |
4 |
Correct |
1 ms |
6492 KB |
Output is correct |
5 |
Correct |
1 ms |
6492 KB |
Output is correct |
6 |
Correct |
1 ms |
6492 KB |
Output is correct |
7 |
Correct |
1 ms |
6492 KB |
Output is correct |
8 |
Correct |
1 ms |
6492 KB |
Output is correct |
9 |
Correct |
1 ms |
6492 KB |
Output is correct |
10 |
Correct |
1 ms |
6488 KB |
Output is correct |
11 |
Correct |
1 ms |
6492 KB |
Output is correct |
12 |
Correct |
1 ms |
6492 KB |
Output is correct |
13 |
Correct |
1 ms |
6572 KB |
Output is correct |
14 |
Correct |
1 ms |
6492 KB |
Output is correct |
15 |
Correct |
2 ms |
6612 KB |
Output is correct |
16 |
Correct |
1 ms |
6492 KB |
Output is correct |
17 |
Correct |
1 ms |
6492 KB |
Output is correct |
18 |
Correct |
1 ms |
6492 KB |
Output is correct |
19 |
Correct |
1 ms |
6492 KB |
Output is correct |
20 |
Correct |
2779 ms |
421236 KB |
Output is correct |
21 |
Correct |
1264 ms |
421312 KB |
Output is correct |
22 |
Correct |
1281 ms |
420816 KB |
Output is correct |
23 |
Correct |
1383 ms |
421812 KB |
Output is correct |
24 |
Correct |
1718 ms |
421444 KB |
Output is correct |
25 |
Correct |
2621 ms |
421976 KB |
Output is correct |
26 |
Correct |
2633 ms |
421200 KB |
Output is correct |
27 |
Correct |
2662 ms |
420976 KB |
Output is correct |
28 |
Correct |
2749 ms |
421376 KB |
Output is correct |
29 |
Correct |
2376 ms |
419048 KB |
Output is correct |
30 |
Correct |
2577 ms |
421200 KB |
Output is correct |
31 |
Correct |
2612 ms |
421208 KB |
Output is correct |
32 |
Correct |
2602 ms |
422672 KB |
Output is correct |
33 |
Correct |
2627 ms |
421052 KB |
Output is correct |
34 |
Correct |
1930 ms |
391288 KB |
Output is correct |
35 |
Correct |
2602 ms |
422064 KB |
Output is correct |
36 |
Correct |
2670 ms |
421564 KB |
Output is correct |
37 |
Correct |
1302 ms |
421168 KB |
Output is correct |
38 |
Correct |
1379 ms |
421052 KB |
Output is correct |
39 |
Correct |
1407 ms |
421056 KB |
Output is correct |
40 |
Correct |
1776 ms |
421420 KB |
Output is correct |
41 |
Correct |
2671 ms |
421460 KB |
Output is correct |
42 |
Correct |
2683 ms |
421412 KB |
Output is correct |
43 |
Correct |
2693 ms |
421484 KB |
Output is correct |
44 |
Correct |
2846 ms |
421276 KB |
Output is correct |
45 |
Correct |
2357 ms |
418388 KB |
Output is correct |
46 |
Correct |
2778 ms |
421200 KB |
Output is correct |
47 |
Correct |
2619 ms |
421428 KB |
Output is correct |
48 |
Correct |
2665 ms |
422376 KB |
Output is correct |
49 |
Correct |
2687 ms |
421468 KB |
Output is correct |
50 |
Correct |
1946 ms |
391324 KB |
Output is correct |
51 |
Correct |
2661 ms |
422664 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
2 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6488 KB |
Output is correct |
4 |
Correct |
1 ms |
6492 KB |
Output is correct |
5 |
Correct |
1 ms |
6492 KB |
Output is correct |
6 |
Correct |
1 ms |
6492 KB |
Output is correct |
7 |
Correct |
1 ms |
6492 KB |
Output is correct |
8 |
Correct |
1 ms |
6492 KB |
Output is correct |
9 |
Correct |
1 ms |
6492 KB |
Output is correct |
10 |
Correct |
1 ms |
6488 KB |
Output is correct |
11 |
Correct |
1 ms |
6492 KB |
Output is correct |
12 |
Correct |
1 ms |
6492 KB |
Output is correct |
13 |
Correct |
1 ms |
6572 KB |
Output is correct |
14 |
Correct |
1 ms |
6492 KB |
Output is correct |
15 |
Correct |
2 ms |
6612 KB |
Output is correct |
16 |
Correct |
1 ms |
6492 KB |
Output is correct |
17 |
Correct |
1 ms |
6492 KB |
Output is correct |
18 |
Correct |
1 ms |
6492 KB |
Output is correct |
19 |
Correct |
1 ms |
6492 KB |
Output is correct |
20 |
Correct |
2779 ms |
421236 KB |
Output is correct |
21 |
Correct |
1264 ms |
421312 KB |
Output is correct |
22 |
Correct |
1281 ms |
420816 KB |
Output is correct |
23 |
Correct |
1383 ms |
421812 KB |
Output is correct |
24 |
Correct |
1718 ms |
421444 KB |
Output is correct |
25 |
Correct |
2621 ms |
421976 KB |
Output is correct |
26 |
Correct |
2633 ms |
421200 KB |
Output is correct |
27 |
Correct |
2662 ms |
420976 KB |
Output is correct |
28 |
Correct |
2749 ms |
421376 KB |
Output is correct |
29 |
Correct |
2376 ms |
419048 KB |
Output is correct |
30 |
Correct |
2577 ms |
421200 KB |
Output is correct |
31 |
Correct |
2612 ms |
421208 KB |
Output is correct |
32 |
Correct |
2602 ms |
422672 KB |
Output is correct |
33 |
Correct |
2627 ms |
421052 KB |
Output is correct |
34 |
Correct |
1930 ms |
391288 KB |
Output is correct |
35 |
Correct |
2602 ms |
422064 KB |
Output is correct |
36 |
Correct |
1 ms |
6492 KB |
Output is correct |
37 |
Correct |
2 ms |
6492 KB |
Output is correct |
38 |
Correct |
1 ms |
6492 KB |
Output is correct |
39 |
Correct |
3717 ms |
433140 KB |
Output is correct |
40 |
Correct |
3714 ms |
443328 KB |
Output is correct |
41 |
Correct |
3767 ms |
443204 KB |
Output is correct |
42 |
Correct |
3197 ms |
359316 KB |
Output is correct |
43 |
Correct |
4818 ms |
322980 KB |
Output is correct |
44 |
Correct |
2857 ms |
311896 KB |
Output is correct |
45 |
Correct |
4083 ms |
444388 KB |
Output is correct |
46 |
Correct |
4754 ms |
318152 KB |
Output is correct |
47 |
Correct |
1 ms |
6488 KB |
Output is correct |
48 |
Correct |
2019 ms |
22396 KB |
Output is correct |
49 |
Correct |
2032 ms |
22344 KB |
Output is correct |
50 |
Correct |
2024 ms |
22608 KB |
Output is correct |
51 |
Correct |
2021 ms |
22568 KB |
Output is correct |
52 |
Correct |
2016 ms |
22636 KB |
Output is correct |
53 |
Correct |
2033 ms |
22516 KB |
Output is correct |
54 |
Correct |
2050 ms |
22312 KB |
Output is correct |
55 |
Correct |
2107 ms |
22648 KB |
Output is correct |
56 |
Correct |
2017 ms |
22540 KB |
Output is correct |
57 |
Correct |
2007 ms |
22456 KB |
Output is correct |
58 |
Correct |
2305 ms |
22324 KB |
Output is correct |
59 |
Correct |
2077 ms |
22540 KB |
Output is correct |
60 |
Correct |
2145 ms |
22868 KB |
Output is correct |
61 |
Correct |
2202 ms |
22060 KB |
Output is correct |
62 |
Correct |
2670 ms |
421564 KB |
Output is correct |
63 |
Correct |
1302 ms |
421168 KB |
Output is correct |
64 |
Correct |
1379 ms |
421052 KB |
Output is correct |
65 |
Correct |
1407 ms |
421056 KB |
Output is correct |
66 |
Correct |
1776 ms |
421420 KB |
Output is correct |
67 |
Correct |
2671 ms |
421460 KB |
Output is correct |
68 |
Correct |
2683 ms |
421412 KB |
Output is correct |
69 |
Correct |
2693 ms |
421484 KB |
Output is correct |
70 |
Correct |
2846 ms |
421276 KB |
Output is correct |
71 |
Correct |
2357 ms |
418388 KB |
Output is correct |
72 |
Correct |
2778 ms |
421200 KB |
Output is correct |
73 |
Correct |
2619 ms |
421428 KB |
Output is correct |
74 |
Correct |
2665 ms |
422376 KB |
Output is correct |
75 |
Correct |
2687 ms |
421468 KB |
Output is correct |
76 |
Correct |
1946 ms |
391324 KB |
Output is correct |
77 |
Correct |
2661 ms |
422664 KB |
Output is correct |
78 |
Execution timed out |
5043 ms |
442528 KB |
Time limit exceeded |
79 |
Halted |
0 ms |
0 KB |
- |