Submission #1124460

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124460		zNatsumi	Reconstruction Project (JOI22_reconstruction)	C++20	7 / 100	139 ms	8248 KiB

reconstruction

#include <bits/stdc++.h>

using namespace std;

#define int long long
using ii = pair<int, int>;
using tp = tuple<int, int, int>;

const int N = 500 + 5,
          M = 1e5 + 5;

int n, m, q, x[N], pa[N], sz[N];
tp edge[M];

int fset(int i){ return i == pa[i] ? i : pa[i] = fset(pa[i]); }
bool uset(int u, int v){
  u = fset(u);
  v = fset(v);
  if(u == v) return false;
  if(sz[u] < sz[v]) swap(u, v);
  pa[v] = u;
  sz[u] += v;
  return true;
}

namespace sub1{
  void solve(){
    for(int t = 1; t <= q; t++){
      for(int i = 1; i <= n; i++) pa[i] = i, sz[i] = 1;
      vector<tp> tmp;
      for(int i = 1; i <= m; i++) tmp.emplace_back(edge[i]);

      sort(tmp.begin(), tmp.end(), [&](tp a, tp b){
              return abs(get<2>(a) - x[t]) < abs(get<2>(b) - x[t]);
           });
      int res = 0;
      for(auto [u, v, w] : tmp) if(uset(u, v)) res += abs(w - x[t]);

      cout << res << "\n";
    }
  }
}

namespace sub2{
  ii query[M];
  int res[M], ptr[N];
  vector<int> weight[N];
  void solve(){
    for(int i = 1; i <= q; i++) query[i] = {x[i], i};
    sort(query + 1, query + q + 1);
    for(int i = 1; i <= m; i++){
      int u, v, w; tie(u, v, w) = edge[i];
      if(u > v) swap(u, v);
      weight[u].push_back(w);
    }
    for(int i = 1; i < n; i++) sort(weight[i].begin(), weight[i].end());

    for(int i = 1; i <= q; i++){
      for(int i = 1; i < n; i++){
        while(weight[i][ptr[i] + 1] <= query[i].first) ptr[i]++;
        int tmp = abs(weight[i][ptr[i]] - query[i].first);
        if(ptr[i] + 1 < weight[i].size()) tmp = min(tmp, abs(weight[i][ptr[i] + 1] - query[i].first));
        res[query[i].second] += tmp;
      }
    }
    for(int i = 1; i <= q; i++) cout << res[i] << "\n";
  }
}

int32_t main(){
  cin.tie(0)->sync_with_stdio(0);
//  #define task "test"
//  if(fopen(task ".inp", "r")){
//    freopen(task ".inp", "r", stdin);
//    freopen(task ".out", "w", stdout);
//  }
  cin >> n >> m;
  for(int i = 1; i <= m; i++){
    int u, v, w; cin >> u >> v >> w;
    edge[i] = {u, v, w};
  }
  cin >> q;
  for(int i = 1; i <= q; i++) cin >> x[i];

  if(q <= 10) sub1::solve();
  else sub2::solve();

  return 0;
}

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