제출 #884639

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
884639		MilosMilutinovic	Reconstruction Project (JOI22_reconstruction)	C++14	100 / 100	3307 ms	31892 KiB

reconstruction

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<int> u(m);
  vector<int> v(m);
  vector<int> w(m);
  for (int i = 0; i < m; i++) {
    cin >> u[i] >> v[i] >> w[i];
    --u[i]; --v[i];
  }
  {
    vector<int> order(m);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int i, int j) {
      return w[i] < w[j];
    });
    vector<int> new_u(m);
    vector<int> new_v(m);
    vector<int> new_w(m);
    for (int i = 0; i < m; i++) {
      new_u[i] = u[order[i]];
      new_v[i] = v[order[i]];
      new_w[i] = w[order[i]];
    }
    u = new_u;
    v = new_v;
    w = new_w;
  }
  vector<int> par(n);
  vector<int> sz(n);
  auto Init = [&]() {
    for (int i = 0; i < n; i++) {
      par[i] = i;
      sz[i] = 1;
    }
  };
  function<int(int)> Get = [&](int x) {
    return par[x] == x ? x : par[x] = Get(par[x]);
  };
  auto Unite = [&](int x, int y) {
    x = Get(x);
    y = Get(y);
    if (x == y) {
      return;
    }
    if (sz[x] < sz[y]) {
      swap(x, y);
    }
    sz[x] += sz[y];
    par[y] = x;
  };
  auto Same = [&](int x, int y) {
    return Get(x) == Get(y);
  };
  vector<tuple<int, int, int>> vec;
  for (int i = 0; i < m; i++) {
    int from = -1, to = 1e9;
    {
      Init();
      int ptr = i - 1;
      while (ptr >= 0) {
        Unite(u[ptr], v[ptr]);
        if (Same(u[i], v[i])) {
          break;
        }
        ptr -= 1;
      }
      if (ptr >= 0) {
        from = (w[i] + w[ptr]) / 2 + 1;
      }
      if (from <= w[i]) {
        vec.emplace_back(from, -1, +w[i]);
        vec.emplace_back(w[i], +1, -w[i]);
      }
    }
    {
      Init();
      int ptr = i + 1;
      while (ptr < m) {
        Unite(u[ptr], v[ptr]);
        if (Same(u[i], v[i])) {
          break;
        }
        ptr += 1;
      }
      if (ptr < m) {
        to = (w[i] + w[ptr]) / 2;
      }
      vec.emplace_back(w[i], +1, -w[i]);
      vec.emplace_back(to + 1, -1, +w[i]);
    }
  }
  sort(vec.begin(), vec.end());
  int coeff = 0;
  long long add = 0;
  int ptr = 0;
  int q;
  cin >> q;
  while (q--) {
    int x;
    cin >> x;
    while (ptr < (int) vec.size() && get<0>(vec[ptr]) <= x) {
      coeff += get<1>(vec[ptr]);
      add += get<2>(vec[ptr]);
      ptr += 1;
    }
    cout << coeff * 1LL * x + add << '\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