Submission #963890

#	Time	Username	Problem	Language	Result	Execution time	Memory
963890		huutuan	Reconstruction Project (JOI22_reconstruction)	C++14	100 / 100	1316 ms	43232 KiB

reconstruction

#include<bits/stdc++.h>

using namespace std;

#define int long long

struct DSURollback{
   vector<int> lab;
   int cc;
   void init(int n){
      lab.assign(n+1, -1);
      cc=n;
   }
   int find_set(int u){
      return lab[u]<0?u:lab[u]=find_set(lab[u]);
   }
   bool union_sets(int u, int v){
      u=find_set(u); v=find_set(v);
      if (u!=v){
         if (lab[u]>lab[v]) swap(u, v);
         lab[u]+=lab[v];
         lab[v]=u;
         --cc;
         return 1;
      }
      return 0;
   }
   bool same(int u, int v){
      return find_set(u)==find_set(v);
   }
} dsu;

struct Edge{
   int u, v, w;
   Edge (int _u=0, int _v=0, int _w=0){
      u=_u, v=_v, w=_w;
   }
   bool operator<(const Edge &b){
      return make_tuple(w, u, v)<make_tuple(b.w, b.u, b.v);
   }
};

const int N=510, M=1e5+10, Q=1e6+10;
int n, m, q, nxt[M];
Edge a[M];
int b[Q];

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n >> m;
   for (int i=1; i<=m; ++i) cin >> a[i].u >> a[i].v >> a[i].w;
   dsu.init(n);
   sort(a+1, a+m+1);
   cin >> q;
   for (int i=1; i<=q; ++i) cin >> b[i];
   vector<pair<int, pair<int, int>>> v;
   for (int i=1; i<=m; ++i){
      dsu.init(n);
      int j;
      for (j=i+1; j<=m; ++j){
         dsu.union_sets(a[j].u, a[j].v);
         if (dsu.same(a[i].u, a[i].v)) break;
      }
      int rval=j==m+1?((int)1e9)+1:a[i].w+(a[j].w-a[i].w+1)/2;
      dsu.init(n);
      for (j=i-1; j>=1; --j){
         dsu.union_sets(a[j].u, a[j].v);
         if (dsu.same(a[i].u, a[i].v)) break;
      }
      int lval=j==0?-1:a[i].w-(a[i].w-a[j].w)/2;
      v.push_back({lval, {i, 1}});
      v.push_back({a[i].w, {i, 2}});
      v.push_back({rval, {i, 3}});
   }
   sort(v.begin(), v.end());
   int add=0, mul=0;
   for (int i=1, j=0; i<=q; ++i){
      while (j<(int)v.size() && v[j].first<=b[i]){
         if (v[j].second.second==1){
            add+=a[v[j].second.first].w;
            mul-=1;
         }else if (v[j].second.second==2){
            add-=a[v[j].second.first].w*2;
            mul+=2;
         }else{
            add+=a[v[j].second.first].w;
            mul-=1;
         }
         ++j;
      }
      cout << add+mul*b[i] << '\n';
   }
   return 0;
}

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