Submission #1061017

#TimeUsernameProblemLanguageResultExecution timeMemory
106101712345678Reconstruction Project (JOI22_reconstruction)C++17
7 / 100
5095 ms8344 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define int long long const int nx=5e2+5, mx=1e5+5; ll n, m, a[mx], b[mx], w[mx], dsu[nx], x, q; int find(int x) { if (dsu[x]==x) return x; return dsu[x]=find(dsu[x]); } int32_t main() { cin.tie(NULL)->sync_with_stdio(false); cin>>n>>m; for (int i=1; i<=m; i++) cin>>a[i]>>b[i]>>w[i]; cin>>q; while (q--) { cin>>x; vector<pair<ll, ll>> edg; for (int i=1; i<=n; i++) dsu[i]=i; for (int i=1; i<=m; i++) edg.push_back({abs(w[i]-x), i}); sort(edg.begin(), edg.end()); ll res=0; for (auto [k, idx]:edg) { if (find(a[idx])==find(b[idx])) continue; res+=k; dsu[find(a[idx])]=find(b[idx]); } cout<<res<<'\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...