제출 #1217096

#제출 시각아이디문제언어결과실행 시간메모리
1217096noyancanturkReconstruction Project (JOI22_reconstruction)C++20
42 / 100
5093 ms16096 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[lllim]; 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){ //cerr<<l<<' '<<r<<'\n'; 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(); //cerr<<"here\n"; vector<int>gol,gor; for(int i:inds){ //cerr<<e[i].x<<' '<<e[i].y<<'\n'; if(dsu.unite(e[i].x,e[i].y)){ //cerr<<"aaa\n"; 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){ //cerr<<"www\n"; if(l<=mid-1)gol.pb(i); }else{ //cerr<<"???\n"; 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(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 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...