Submission #1205180

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205180		abczz	Reconstruction Project (JOI22_reconstruction)	C++20	3 / 100	48 ms	3516 KiB

reconstruction

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

using namespace std;

ll n, m, a, b, c, P[250];
priority_queue <array<ll, 2>, vector<array<ll, 2>>, greater<array<ll, 2>>> pq;
vector <array<ll, 3>> E;
ll dsu(ll u) {
  if (P[u] == u) return u;
  else return P[u] = dsu(P[u]);
}
int main() {
  cin >> n >> m;
  for (int i=0; i<m; ++i) {
    cin >> a >> b >> c;
    --a, --b;
    E.push_back({a, b, c});
  }
  ll q;
  cin >> q;
  while (q--) {
    cin >> a;
    ll f = 0;
    for (int i=0; i<n; ++i) P[i] = i;
    for (int i=0; i<m; ++i) {
      pq.push({abs(E[i][2]-a), i});
    }
    while (!pq.empty()) {
      auto [w, id] = pq.top();
      pq.pop();
      a = E[id][0], b = E[id][1];
      a = dsu(a), b = dsu(b);
      if (a != b) {
        P[a] = b;
        f += w;
      }
    }
    cout << f << '\n';
  }
}

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