Submission #1169327

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169327		zNatsumi	Reconstruction Project (JOI22_reconstruction)	C++20	100 / 100	368 ms	70464 KiB

reconstruction

#include <bits/stdc++.h>

using namespace std;

using ii = array<int, 2>;
using tp = array<int, 3>;

const int N = 1e6 + 5;

int n, m, q, X[N];
vector<ii> ad[N];
tp edge[N];

struct DSU{
  int pa[N], sz[N];

  void mset(int n){
    for(int i = 1; i <= n; i++) pa[i] = i, sz[i] = 1;
  }
  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] += sz[v];
    return true;
  }
};

namespace sub12{
  DSU d;

  void solve(){
    for(int t = 1; t <= q; t++){
      sort(edge + 1, edge + m + 1, [&](tp x, tp y){
              return abs(x[0] - X[t]) < abs(y[0] - X[t]);
           });
      d.mset(n);
      long long res = 0;
      for(auto [w, u, v] : edge)
        if(d.uset(u, v)) res += 1LL*abs(w - X[t]);
      cout << res << "\n";
    }
  }
}

namespace sub3{
  vector<int> weight[N];
  int ptr[N];
  vector<ii> query;

  void solve(){
    for(int i = 1; i < n; i++){
      for(auto [j, w] : ad[i]) if(j == i + 1) weight[i].push_back(w);
      sort(weight[i].begin(), weight[i].end());
    }
    for(int i = 1; i <= q; i++) query.push_back({X[i], i});
    sort(query.begin(), query.end());

    for(int t = 1; t <= q; t++){
      long long res = 0;
      for(int i = 1; i < n; i++){
        while(ptr[i] + 1 < weight[i].size() && weight[i][ptr[i] + 1] <= X[t]) ptr[i]++;
        int tmp = abs(X[t] - weight[i][ptr[i]]);
        if(X[t] >= weight[i][ptr[i]] && ptr[i] + 1 < weight[i].size()) tmp = min(tmp, abs(X[t] - weight[i][ptr[i] + 1]));
        res += tmp;
      }
      cout << res << "\n";
    }
  }
}

namespace sub4{
  DSU d;
  bool del[N];
  vector<tp> event;

  void solve(){
    sort(edge + 1, edge + m + 1);

    for(int i = 1; i <= m; i++){
      d.mset(n);
      int L = 0;
      for(int j = i; j >= 1; j--)
        if(!del[j] && !d.uset(edge[j][1], edge[j][2])){
          L = j;
          break;
        }
      if(L){
        del[L] = true;
        int mid = (edge[i][0] + edge[L][0] + 1) / 2;
        event.push_back({mid, edge[i][0] + edge[L][0], -2}); // 3
      }else{
        event.push_back({0, edge[i][0], -1}); // 1
      }
      event.push_back({edge[i][0], -2 * edge[i][0], +2}); // 2
    }
    sort(event.begin(), event.end());

    int ptr = 0;
    long long A = 0, B = 0;
    for(int t = 1; t <= q; t++){
      while(ptr < event.size() && event[ptr][0] <= X[t]){
        A += event[ptr][1];
        B += event[ptr][2];
        ptr += 1;
      }
      cout << A + B * X[t] << "\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;
  bool chks3 = true;
  for(int i = 1; i <= m; i++){
    int u, v, w; cin >> u >> v >> w;
    ad[u].push_back({v, w});
    ad[v].push_back({u, w});
    edge[i] = {w, u, v};
    if(v != u + 1) chks3 = false;
  }
  cin >> q;
  for(int i = 1; i <= q; i++) cin >> X[i];

//  if(q <= 10) sub12::solve();
//  else if(chks3) sub3::solve();
  sub4::solve();

  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