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...