Submission #1217096

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217096		noyancanturk	Reconstruction Project (JOI22_reconstruction)	C++20	42 / 100	5093 ms	16096 KiB

reconstruction

#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';
}

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 0 / 7
• Subtask 4: 0 / 28
• Subtask 5: 35 / 35
• Subtask 6: 0 / 23