Submission #83331

#TimeUsernameProblemLanguageResultExecution timeMemory
83331Bodo171Election Campaign (JOI15_election_campaign)C++14
100 / 100
508 ms151728 KiB
#include <iostream> #include <fstream> #include <vector> using namespace std; const int nmax=100005; struct qr { int n1,n2,cost; }; vector<qr> L[nmax]; vector<int> v[nmax]; int tt[20][nmax]; int l[nmax],r[nmax],aib[nmax],dp[nmax],sons[nmax]; int n,m,i,j,nr,a,b,c,al,bl,t; inline int lbit(int x) { return ((x^(x-1))&x); } void update(int poz,int val) { for(int idx=poz;idx<=n;idx+=lbit(idx)) aib[idx]+=val; } int compute(int poz) { int ret=0; for(int idx=poz;idx>0;idx-=lbit(idx)) ret+=aib[idx]; return ret; } void dfs(int x) { l[x]=++nr; for(int i=0;i<v[x].size();i++) if(!l[v[x][i]]) { tt[0][v[x][i]]=x; dfs(v[x][i]); } r[x]=nr; } void chef() { for(int i=1;i<=16;i++) for(int j=1;j<=n;j++) tt[i][j]=tt[i-1][tt[i-1][j]]; } bool cup(int a,int b) { return (l[a]<=l[b]&&l[b]<=r[a]); } int lca(int a,int b) { int stram=0; for(int p=16;p>=0;p--) { stram=tt[p][a]; if(stram&&(!cup(stram,b))) a=stram; } if(!cup(a,b)) a=tt[0][a]; return a; } int nxt(int a,int L) { if(a==L) return 0; for(int p=16;p>=0;p--) if(tt[p][a]&&(!cup(tt[p][a],L))) a=tt[p][a]; return a; } void defeseu(int x) { for(int i=0;i<v[x].size();i++) if(l[v[x][i]]>l[x]) defeseu(v[x][i]); int sum=0; for(int i=0;i<v[x].size();i++) sum+=dp[v[x][i]]; dp[x]=sum;sons[x]=sum; for(int i=0;i<L[x].size();i++) { a=L[x][i].n1;b=L[x][i].n2;c=L[x][i].cost; al=nxt(a,x);bl=nxt(b,x); if(sum-dp[al]-dp[bl]+compute(l[a])+compute(l[b])+c+sons[a]*(a!=x)+sons[b]*(b!=x)>dp[x]) dp[x]=sum-dp[al]-dp[bl]+compute(l[a])+compute(l[b])+c+sons[a]*(a!=x)+sons[b]*(b!=x); } int nod; for(int i=0;i<v[x].size();i++) if(l[v[x][i]]>l[x]) { nod=v[x][i]; sum-=dp[nod]; update(l[nod],sum); update(r[nod]+1,-sum); sum+=dp[nod]; } } int main() { // freopen("data.in","r",stdin); ios_base::sync_with_stdio(false); cin>>n; for(i=1;i<=n-1;i++) { cin>>a>>b; v[a].push_back(b); v[b].push_back(a); } dfs(1); chef(); cin>>m; for(i=1;i<=m;i++) { cin>>a>>b>>c; t=lca(a,b); L[t].push_back({a,b,c}); } defeseu(1); cout<<dp[1]; return 0; }

Compilation message (stderr)

election_campaign.cpp: In function 'void dfs(int)':
election_campaign.cpp:34:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~
election_campaign.cpp: In function 'void defeseu(int)':
election_campaign.cpp:75:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~
election_campaign.cpp:79:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~
election_campaign.cpp:82:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<L[x].size();i++)
                 ~^~~~~~~~~~~~
election_campaign.cpp:90:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int i=0;i<v[x].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...