제출 #1124435

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1124435		zNatsumi	Reconstruction Project (JOI22_reconstruction)	C++20	0 / 100	1 ms	328 KiB

reconstruction

#include <bits/stdc++.h>

using namespace std;

using tp = tuple<int, int, int>;
const int N = 500 + 5,
          M = 1e5 + 5;

int n, m, q, pa[N], sz[N];
tp edge[N];

int fset(int i){ return i == pa[i] ? i : pa[i] = fset(pa[i]); }
bool uset(int u, int v){
  u = fset(u);
  v = fset(v);
  if(u == v) return false;
  if(sz[u] < sz[v]) swap(u, v);
  pa[v] = u;
  sz[u] += v;
  return true;
}

int32_t main(){
  cin.tie(0)->sync_with_stdio(0);
//  #define task "test"
//  if(fopen(task ".inp", "r")){
//    freopen(task ".inp", "r", stdin);
//    freopen(task ".out", "w", stdout);
//  }
  cin >> n >> m;
  for(int i = 1; i <= m; i++){
    int u, v, w; cin >> u >> v >> w;
    edge[i] = {u, v, w};
  }
  cin >> q;
  while(q--){
    int x; cin >> x;
    for(int i = 1; i <= n; i++) pa[i] = i, sz[i] = 1;
    vector<tp> tmp;
    for(int i = 1; i <= m; i++) tmp.emplace_back(get<0>(edge[i]), get<1>(edge[i]), abs(get<2>(edge[i]) - x));

    sort(tmp.begin(), tmp.end(), [&](tp x, tp y){
            return get<2>(x) < get<2>(y);
         });
    int res = 0;
    for(auto [u, v, w] : tmp){
      if(uset(u, v)){
        res += w;
      }
    }
    cout << res << "\n";
  }

  return 0;
}

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