Submission #219391

#	Time	Username	Problem	Language	Result	Execution time	Memory
219391		MKopchev	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	252 ms	32632 KiB

election_campaign

#include<bits/stdc++.h>
using namespace std;
const int nmax=1e5+42;
int n,q;
vector<int> adj[nmax];

vector<int> seen[nmax];

struct path
{
    int u,v,gain;
};

path inp[nmax];

int up[20][nmax],depth[nmax];

int in[nmax],out[nmax],t=0;
void dfs(int node,int parent)
{
    t++;
    in[node]=t;

    up[0][node]=parent;
    depth[node]=1+depth[parent];
    for(auto k:adj[node])
        if(k!=parent)dfs(k,node);

    out[node]=t;
}

int lca(int u,int v)
{
    if(depth[u]>depth[v])swap(u,v);
    for(int i=19;i>=0;i--)
        if(depth[u]<=depth[v]-(1<<i))v=up[i][v];
    if(u==v)return u;
    for(int i=19;i>=0;i--)
        if(up[i][u]!=up[i][v])u=up[i][u],v=up[i][v];
    return up[0][u];
}

long long dp[nmax];
long long sum[nmax];

long long fenwick[nmax];
void update(int pos,long long val)
{
    while(pos<=n)
    {
        fenwick[pos]+=val;
        pos=pos+(pos&(-pos));
    }
}
long long query(int pos)
{
    long long ret=0;
    while(pos)
    {
        ret=ret+fenwick[pos];
        pos=pos-(pos&(-pos));
    }
    return ret;
}
long long ask(int l,int r)
{
    if(l>r)return 0;
    return query(r)-query(l-1);
}
long long take_path(int lower,int upper)
{
    long long ret=ask(in[upper]+1,in[lower]);

    return ret;
}
long long rec(int node,int parent)
{
    long long ret=0;
    //ignore the node
    for(auto k:adj[node])
        if(k!=parent)ret=ret+rec(k,node);

    sum[node]=ret;

    for(auto which:seen[node])
    {
        long long current=inp[which].gain+take_path(inp[which].u,node)+take_path(inp[which].v,node)+sum[node];

        //cout<<"node= "<<node<<" taken_path= "<<inp[which].u<<" "<<inp[which].v<<" "<<inp[which].gain<<" -> "<<current<<" : "<<take_path(inp[which].u,node)<<" "<<take_path(inp[which].v,node)<<" "<<sum[node]<<endl;

        ret=max(ret,current);
    }

    //cout<<node<<" -> "<<ret<<" "<<sum[node]<<endl;
    dp[node]=ret;

    update(in[node],sum[node]-dp[node]);
    update(out[node]+1,-(sum[node]-dp[node]));

    return ret;
}
int main()
{
    scanf("%i",&n);
    int u,v;
    for(int i=1;i<n;i++)
    {
        scanf("%i%i",&u,&v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(1,1);
    for(int st=1;st<20;st++)
        for(int i=1;i<=n;i++)
            up[st][i]=up[st-1][up[st-1][i]];

    scanf("%i",&q);
    for(int i=1;i<=q;i++)
    {
        scanf("%i%i%i",&inp[i].u,&inp[i].v,&inp[i].gain);
        seen[lca(inp[i].u,inp[i].v)].push_back(i);
    }

    printf("%lld\n",rec(1,0));
    return 0;
}

Compilation message (stderr)

election_campaign.cpp: In function 'int main()':
election_campaign.cpp:104:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
election_campaign.cpp:108:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i%i",&u,&v);
         ~~~~~^~~~~~~~~~~~~~
election_campaign.cpp:118:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&q);
     ~~~~~^~~~~~~~~
election_campaign.cpp:121:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i%i%i",&inp[i].u,&inp[i].v,&inp[i].gain);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 30 / 30
• Subtask 5: 10 / 10
• Subtask 6: 40 / 40