This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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<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 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,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());
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,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);
}
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 (stderr)
reconstruction.cpp: In function 'int main()':
reconstruction.cpp:170: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]
170 | while(pa+1<add.size() && add[pa+1].first<=2*x) {
| ~~~~^~~~~~~~~~~
reconstruction.cpp:175: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]
175 | while(pd+1<del.size() && del[pd+1].first<=2*x) {
| ~~~~^~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |