Submission #1061209

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061209		kunzaZa183	Reconstruction Project (JOI22_reconstruction)	C++17	3 / 100	5059 ms	6740 KiB

reconstruction

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
  int n, m;
  cin >> n >> m;

  const int maxm = 1e5, maxn = 500;

  struct edge {
    int a, b, we;
  };
  vector<edge> elist(maxm);

  for (int i = 0; i < m; i++)
    cin >> elist[i].a >> elist[i].b >> elist[i].we;

  int qs;
  cin >> qs;
  while (qs--) {
    vector<int> dsu(maxn);
    iota(dsu.begin(), dsu.end(), 0);

    int x;
    cin >> x;
    vector<edge> ve(elist);
    for (int i = 0; i < m; i++) {
      ve[i].we = abs(ve[i].we - x);
    }

    sort(ve.begin(), ve.end(), [&](edge a, edge b) { return a.we < b.we; });

    function<int(int)> par = [&](int cur) {
      if (dsu[cur] == cur)
        return cur;
      dsu[cur] = par(dsu[cur]);
      return dsu[cur];
    };

    int cost = 0;
    for (auto a : ve) {
      if (par(a.a) != par(a.b)) {
        cost += a.we;
        dsu[par(a.a)] = par(a.b);
      }
    }

    cout << cost << "\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