Submission #219388

#	Time	Username	Problem	Language	Result	Execution time	Memory
219388		MKopchev	Election Campaign (JOI15_election_campaign)	C++14	20 / 100	1089 ms	30712 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];

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

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 take_path(int lower,int upper)
{
    long long ret=0;

    //cout<<"lower= "<<lower<<" upper= "<<upper<<endl;

    while(lower!=upper)
    {
        ret=ret+sum[lower]-dp[lower];
        lower=up[0][lower];

        //cout<<"ret= "<<ret<<" lower= "<<lower<<endl;
    }

    //cout<<"---"<<endl;

    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;

    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:83:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
election_campaign.cpp:87: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:97:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&q);
     ~~~~~^~~~~~~~~
election_campaign.cpp:100: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: 0 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 30
• Subtask 5: 10 / 10
• Subtask 6: 0 / 40