Submission #1217085

#TimeUsernameProblemLanguageResultExecution timeMemory
1217085noyancanturkReconstruction Project (JOI22_reconstruction)C++20
42 / 100
5093 ms15444 KiB
#include<bits/stdc++.h> using namespace std; #define int int64_t #define pb push_back const int lim=510; const int llim=1e5+100; const int lllim=1e6+100; struct { int parent[lim]; void init(){ for(int i=0;i<lim;i++)parent[i]=i; } int find(int i){ if(i==parent[i])return i; return parent[i]=find(parent[i]); } int unite(int i,int j){ i=find(i),j=find(j); if(i==j)return 0; parent[i]=j; return 1; } }dsu; struct edge{ int x,y,z; }; edge e[llim]; int quer[lllim]; int ans[llim]; int x; bool cmp(int i,int j){ int dif1=abs(e[i].z-x); int dif2=abs(e[j].z-x); if(dif1!=dif2)return dif1<dif2; return i<j; } void solve(int l,int r,vector<int>&inds){ int mid=l+r>>1; x=quer[mid]; for(int i=0;i+1<inds.size();i++){ if(cmp(inds[i],inds[i+1]))continue; sort(inds.begin(),inds.end(),cmp); break; } dsu.init(); vector<int>gol,gor; for(int i:inds){ if(dsu.unite(e[i].x,e[i].y)){ ans[mid]+=abs(e[i].z-x); if(l<=mid-1)gol.pb(i); if(mid+1<=r)gor.pb(i); }else if(e[i].z<x){ if(l<=mid-1)gol.pb(i); }else{ if(mid+1<=r)gor.pb(i); } } if(l<=mid-1)solve(l,mid-1,gol); if(mid+1<=r)solve(mid+1,r,gor); } signed main(){ int n,m; cin>>n>>m; for(int i=0;i<m;i++){ cin>>e[i].x>>e[i].y>>e[i].z; } int q; cin>>q; for(int i=0;i<q;i++)cin>>quer[i]; vector<int>v; for(int i=0;i<m;i++)v.pb(i); solve(0,q-1,v); for(int i=0;i<q;i++)cout<<ans[i]<<'\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...