Submission #917042

#TimeUsernameProblemLanguageResultExecution timeMemory
917042firewaterElection Campaign (JOI15_election_campaign)C++14
10 / 100
108 ms27272 KiB
#include<bits/stdc++.h> #define fs first #define sn second #define mp make_pair #define N 100100 #define ll long long using namespace std; ll n,m,ans,x,y,z,w,tot,h[N],f[N],sz[N],hs[N],top[N],fa[N],dep[N],dfn[N],low[N],v[N]; vector<pair<pair<ll,ll>,ll> >d[N]; struct rec { ll to,nx; }e[N<<1]; void addl(ll x,ll y) { e[++tot].to=y; e[tot].nx=h[x]; h[x]=tot; return; } struct Tree { #define ls x*2 #define rs x*2+1 ll s[N<<2]; void push_up(ll x) { s[x]=s[ls]+s[rs]; return; } void change(ll x,ll l,ll r,ll y,ll z) { if(l==r){ s[x]=max(s[x],y); return; } ll mid=l+r>>1; if(y<=r)change(ls,l,mid,y,z); else change(rs,mid+1,r,y,z); push_up(x); return; } ll ask(ll x,ll L,ll R,ll l,ll r) { if(L==R)return s[x]; ll mid=L+R>>1; if(mid<=r)return ask(ls,L,mid,l,r); else if(mid>l)return ask(rs,mid+1,R,l,r); else return ask(ls,L,mid,l,mid)+ask(rs,mid+1,R,mid+1,r); } }T; void dfs(ll x) { sz[x]=1; for(ll i=h[x];i;i=e[i].nx){ ll y=e[i].to; if(y==fa[x])continue; fa[y]=x; dep[y]=dep[x]+1; dfs(y); sz[x]+=sz[y]; if(sz[y]>sz[hs[x]])hs[x]=y; } return; } void dfs1(ll x,ll anc) { dfn[x]=++w; top[x]=anc; if(hs[x])dfs1(hs[x],anc); for(ll i=h[x];i;i=e[i].nx){ ll y=e[i].to; if(y==fa[x]||y==hs[x])continue; dfs1(y,y); } low[x]=++w; return; } ll lca(ll x,ll y) { while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]])swap(x,y); x=fa[top[x]]; } return (dep[x]<dep[y]?x:y); } ll ask(ll x,ll y) { ll sum=0; while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]])swap(x,y); if(hs[x])sum+=f[hs[x]]; sum+=T.ask(1,1,n,dfn[top[x]],dfn[x])-f[top[x]]; x=fa[top[x]]; } if(dep[x]>dep[y])swap(x,y); if(hs[y])sum+=f[hs[y]]; sum+=T.ask(1,1,n,dfn[x],dfn[y]); return sum; } bool cmp(ll x,ll y) { return dep[x]>dep[y]; } int main() { scanf("%lld",&n); for(ll i=1;i<n;++i){ scanf("%lld%lld",&x,&y); addl(x,y); addl(y,x); } fa[1]=1; dep[1]=1; dfs(1); dfs1(1,1); scanf("%lld",&m); for(ll i=1;i<=m;++i){ scanf("%lld%lld%lld",&x,&y,&z); ll u=lca(x,y); d[u].push_back(mp(mp(x,y),z)); } for(ll i=1;i<=n;++i) v[i]=i; sort(v+1,v+1+n,cmp); for(ll i=1;i<=n;++i){ x=v[i]; f[x]=T.ask(1,1,n,dfn[x],dfn[x]); if(hs[x])f[x]+=f[hs[x]]; for(ll j=0;j<d[x].size();++j){ f[x]=max(f[x],ask(d[x][j].fs.fs,d[x][j].fs.sn)+d[x][j].sn); // printf("...........%d %d %d\n",d[x][j].fs.fs,d[x][j].fs.sn,ask(d[x][j].fs.fs,d[x][j].fs.sn)); } ans=max(ans,f[x]); // printf("%d %d\n",x,f[x]); if(x!=1&&x==top[x])T.change(1,1,n,dfn[fa[x]],f[x]); } printf("%lld\n",ans); return 0; }

Compilation message (stderr)

election_campaign.cpp: In member function 'void Tree::change(long long int, long long int, long long int, long long int, long long int)':
election_campaign.cpp:37:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |   ll mid=l+r>>1;
      |          ~^~
election_campaign.cpp: In member function 'long long int Tree::ask(long long int, long long int, long long int, long long int, long long int)':
election_campaign.cpp:46:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |   ll mid=L+R>>1;
      |          ~^~
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:130:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |   for(ll j=0;j<d[x].size();++j){
      |              ~^~~~~~~~~~~~
election_campaign.cpp:107:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |  scanf("%lld",&n);
      |  ~~~~~^~~~~~~~~~~
election_campaign.cpp:109:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |   scanf("%lld%lld",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~
election_campaign.cpp:117:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |  scanf("%lld",&m);
      |  ~~~~~^~~~~~~~~~~
election_campaign.cpp:119:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |   scanf("%lld%lld%lld",&x,&y,&z);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#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...