Submission #1205185

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205185		abczz	Reconstruction Project (JOI22_reconstruction)	C++20	100 / 100	1238 ms	23196 KiB

reconstruction

#include <iostream>
#include <vector>
#include <array>
#include <queue>
#include <algorithm>
#define ll long long

using namespace std;

vector <array<ll, 3>> E;
vector <ll> V;
ll n, m, q, a, b, c, p = -1, tot = 0, P[500], X[100000], nx[100000], pv[100000];
ll lcnt, rcnt, ltot, rtot;

ll dsu(ll u) {
  if (P[u] == u) return u;
  else return P[u] = dsu(P[u]);
}
void resetdsu() {
  for (int i=0; i<n; ++i) P[i] = i;
}
void redodsu() {
  ll u = p;
  while (u != -1) {
    auto [a, b, c] = E[u];
    a = dsu(a), b = dsu(b);
    P[a] = b;
    u = nx[u];
  }
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cin >> n >> m;
  for (int i=0; i<m; ++i) {
    cin >> a >> b >> c;
    --a, --b;
    E.push_back({a, b, c});
  }
  sort(E.begin(), E.end(), [](auto a, auto b) {
    return a[2] < b[2];
  });
  resetdsu();
  for (int i=m-1; i>=0; --i) {
    X[i] = nx[i] = pv[i] = -1;
    auto [a, b, c] = E[i];
    a = dsu(a), b = dsu(b);
    if (a != b) {
      P[a] = b, nx[i] = p;
      if (p != -1) pv[p] = i;
      p = i;
    }
    else {
      resetdsu();
      ll u = p;
      while (true) {
        auto [a, b, c] = E[u];
        a = dsu(a), b = dsu(b);
        P[a] = b;
        if (dsu(E[i][0]) == dsu(E[i][1])) {
          X[i] = u;
          if (pv[u] != -1) nx[pv[u]] = nx[u];
          if (nx[u] != -1) pv[nx[u]] = pv[u];
          break;
        }
        u = nx[u];
      }
      if (X[i] != p) pv[p] = i, nx[i] = p;
      else {
        if (nx[p] != -1) pv[nx[p]] = i;
        nx[i] = nx[p];
      }
      p = i;
      redodsu();
    }
  }
  rcnt = n-1;
  ll u = 0;
  while (u != -1) {
    rtot += E[u][2];
    u = nx[u];
  }
  vector <array<ll, 2> > A, B;
  for (int i=0; i<m; ++i) {
    //cout << E[i][0] << " " << E[i][1] << " " << E[i][2] << " " << X[i] << endl;
    A.push_back({E[i][2] * 2, i});
    if (X[i] != -1) {
      B.push_back({E[i][2] + E[X[i]][2], i});
    }
  }
  A.push_back({(ll)1e18, -1});
  B.push_back({(ll)1e18, -1});
  sort(B.begin(), B.end());
  cin >> q;
  int i = 0, j = 0;
  while (q--) {
    cin >> a;
    while (true) {
      if (A[i][0] <= B[j][0] && A[i][0] <= 2*a) {
        --rcnt, rtot -= A[i][0]/2;
        ++lcnt, ltot += A[i][0]/2;
        ++i;
      }
      else if (B[j][0] < A[i][0] && B[j][0] <= 2*a) {
        --lcnt, ltot -= E[B[j][1]][2];
        ++rcnt, rtot += E[X[B[j][1]]][2];
        ++j;
      }
      else break;
    }
    //cout << ltot << " " << rtot << " " << i << " " << j << endl;
    cout << lcnt * a - ltot + rtot - rcnt * a << '\n';
  }
}

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