Submission #1077599

#TimeUsernameProblemLanguageResultExecution timeMemory
1077599vjudge1Reconstruction Project (JOI22_reconstruction)C++17
3 / 100
1 ms604 KiB
#include <bits/stdc++.h> #define F first #define S second #define pb push_back #define ppb pop_back #define ep insert #define endl '\n' #define elif else if #define pow pwr #define sqrt sqrtt #define int long long #define ll long long typedef unsigned long long ull; using namespace std; struct edge{ int a,b,w; }; const int N=505,M=1e5+5; int n,sz[N],par[N],m,q,W; edge e[N]; bool cmp(edge x,edge y){ return abs(x.w-W)<abs(y.w-W); } int getpar(int x){ if (x==par[x]) return x; return par[x]=getpar(par[x]); } int link(int x,int y){ x=getpar(x); y=getpar(y); if (x==y) return 0; if (sz[x]>sz[y]) swap(x,y); sz[y]+=sz[x]; par[x]=y; return 1; } int32_t main(){ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); cin>>n>>m; for (int i=1;i<=m;i++) cin>>e[i].a>>e[i].b>>e[i].w; cin>>q; while (q--){ cin>>W; sort(e+1,e+1+m,cmp); for (int i=1;i<=n;i++) par[i]=i,sz[i]=1; int ans=0; for (int i=1;i<=m;i++) ans+=link(e[i].a,e[i].b)*abs(e[i].w-W); cout<<ans<<endl; } return 0; }
#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...