Submission #1061208

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1061208	2024-08-16T07:15:00 Z	kunzaZa183	Reconstruction Project (JOI22_reconstruction)	C++17	0 / 100	5000 ms	2760 KB

reconstruction

#include <bits/stdc++.h>
using namespace std;
int 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
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	2756 KB	Output is correct
2	Correct	9 ms	2760 KB	Output is correct
3	Incorrect	29 ms	2760 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	2756 KB	Output is correct
2	Correct	9 ms	2760 KB	Output is correct
3	Incorrect	29 ms	2760 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #3
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	2756 KB	Output is correct
2	Correct	4 ms	2652 KB	Output is correct
3	Correct	21 ms	2756 KB	Output is correct
4	Execution timed out	5059 ms	2752 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-