Submission #527851

#TimeUsernameProblemLanguageResultExecution timeMemory
527851Koosha_mvElection Campaign (JOI15_election_campaign)C++14
100 / 100
425 ms64196 KiB
#include <bits/stdc++.h> using namespace std; #define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl #define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl #define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl #define eror(x) cout<<#x<<'='<<(x)<<endl #define f_(i,a,b) for(int i=a;i>=b;i--) #define f(i,a,b) for(int i=a;i<b;i++) #define nb(x) __builtin_popcount(x) #define all(v) v.begin(),v.end() #define bit(n,k) (((n)>>(k))&1) #define Add(x,y) x=(x+y)%mod #define maxm(a,b) a=max(a,b) #define minm(a,b) a=min(a,b) #define lst(x) x[x.size()-1] #define sz(x) int(x.size()) #define mp make_pair #define ll long long #define pb push_back #define S second #define F first #define int ll const int N=4e5+99,lg=20; int n,m,cnt=1,st[N],ft[N],h[N],a[N],dp[N],pd[N],par[lg][N],fenwik[N]; vector<int> emp,g[N]; vector<pair<int,int>> solo[N]; vector<pair<pair<int,int>,int>> duo[N]; void add(int x,int val){ for(x++;x<N;x+=x&-x) fenwik[x]+=val; } void add(int l,int r,int val){ add(l,val); add(r,-val); } int get(int x){ int res=0; for(x++;x>0;x-=x&-x) res+=fenwik[x]; return res; } int LCA(int u,int v){ f_(l,lg-1,0){ if(h[u]<=h[par[l][v]]){ v=par[l][v]; } } if(u==v) return u; f_(l,lg-1,0){ if(par[l][u]!=par[l][v]){ u=par[l][u],v=par[l][v]; } } return par[0][u]; } void dfs1(int u,int p){ par[0][u]=p; f(l,1,lg) par[l][u]=par[l-1][par[l-1][u]]; st[u]=cnt++; for(auto v : g[u]){ if(v==p) continue ; h[v]=h[u]+1; dfs1(v,u); } ft[u]=cnt; } void dfs2(int u,int p){ for(auto v : g[u]){ if(v==p) continue ; dfs2(v,u); dp[u]+=dp[v]; pd[u]+=dp[v]; add(st[u]+1,ft[u],dp[v]); add(st[v],ft[v],-dp[v]); } for(auto v : solo[u]){ maxm(dp[u],get(st[v.F])+pd[v.F]+v.S-get(st[u])); } for(auto v : duo[u]){ int sum=pd[v.F.F]+pd[v.F.S]; maxm(dp[u],get(st[v.F.F])+get(st[v.F.S])-get(st[u])-get(st[u])-pd[u]+sum+v.S); } } main(){ ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr); cin>>n; f(i,1,n){ int u,v; cin>>u>>v; g[u].pb(v); g[v].pb(u); } dfs1(1,1); cin>>m; f(i,0,m){ int u,v,x=0,y=0,cost; cin>>u>>v>>cost; if(h[u]>h[v]) swap(u,v); int lca=LCA(u,v); if(lca==u){ solo[u].pb({v,cost}); continue ; } duo[lca].pb({{u,v},cost}); } dfs2(1,1); cout<<dp[1]; }

Compilation message (stderr)

election_campaign.cpp:84:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   84 | main(){
      | ^~~~
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:96:11: warning: unused variable 'x' [-Wunused-variable]
   96 |   int u,v,x=0,y=0,cost;
      |           ^
election_campaign.cpp:96:15: warning: unused variable 'y' [-Wunused-variable]
   96 |   int u,v,x=0,y=0,cost;
      |               ^
#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...