Submission #893091

#TimeUsernameProblemLanguageResultExecution timeMemory
893091alexander707070Security Guard (JOI23_guard)C++14
76 / 100
4035 ms64700 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],c,d,mins; vector<edge> w; unordered_set<int> tree[MAXN]; long long ans; bool ok; 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]; } void dfs(int x,int p,int maxcost,int dx,int dy){ if(maxcost-s[x]-s[mins]>maxs){ maxs=maxcost-s[x]-s[mins]; c=mins; d=x; a=dx; b=dy; } for(int curr:tree[x]){ if(curr==p)continue; if(s[curr]+s[x]>maxcost){ dfs(curr,x,s[curr]+s[x],curr,x); }else{ dfs(curr,x,maxcost,dx,dy); } } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m>>q; mins=1; for(int i=1;i<=n;i++){ cin>>s[i]; ans-=s[i]; maxs=max(maxs,s[i]); dsu[i]=i; sz[i]=1; if(s[i]<s[mins])mins=i; } 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); tree[w[i].from].insert(w[i].to); tree[w[i].to].insert(w[i].from); ans+=s[w[i].from]+s[w[i].to]; } ans+=maxs; cout<<ans<<"\n"; for(int i=1;i<=q;i++){ maxs=0; if(!ok)dfs(mins,0,0,0,0); if(maxs!=0){ ans-=maxs; tree[a].erase(b); tree[b].erase(a); tree[c].insert(d); tree[d].insert(c); }else ok=true; cout<<ans<<"\n"; } return 0; }

Compilation message (stderr)

guard.cpp: In function 'int main()':
guard.cpp:77:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     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...