Submission #893026

#TimeUsernameProblemLanguageResultExecution timeMemory
893026alexander707070Security Guard (JOI23_guard)C++14
50 / 100
270 ms16232 KiB
#include<bits/stdc++.h> #define MAXN 200007 using namespace std; struct edge{ int from,to,cost; }; bool cmp(edge fr,edge sc){ return fr.cost<sc.cost; } int n,m,q,a,b,s[MAXN]; vector<edge> w; long long ans; int dsu[MAXN],sz[MAXN],maxs; int root(int x){ if(dsu[x]==x)return x; dsu[x]=root(dsu[x]); return dsu[x]; } void mergev(int x,int y){ int rootx=root(x); int rooty=root(y); if(sz[rooty]>sz[rootx])swap(rootx,rooty); sz[rootx]+=sz[rooty]; dsu[rooty]=dsu[rootx]; } int main(){ cin>>n>>m>>q; for(int i=1;i<=n;i++){ cin>>s[i]; ans-=s[i]; maxs=max(maxs,s[i]); dsu[i]=i; sz[i]=1; } for(int i=1;i<=m;i++){ cin>>a>>b; w.push_back({a,b,s[a]+s[b]}); } sort(w.begin(),w.end(),cmp); for(int i=0;i<w.size();i++){ if(root(w[i].from)==root(w[i].to))continue; mergev(w[i].from,w[i].to); ans+=s[w[i].from]+s[w[i].to]; } ans+=maxs; cout<<ans<<"\n"; return 0; }

Compilation message (stderr)

guard.cpp: In function 'int main()':
guard.cpp:53:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int i=0;i<w.size();i++){
      |                 ~^~~~~~~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...