oj.uz

Submission #219388

# Submission time Handle Problem Language Result Execution time Memory
219388 2020-04-05T08:27:35 Z MKopchev Election Campaign (JOI15_election_campaign) C++14
20 / 100
 1000 ms 30712 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 7 ms 5248 KB Output is correct
4 Correct 7 ms 5248 KB Output is correct
5 Correct 86 ms 19320 KB Output is correct
6 Correct 60 ms 26872 KB Output is correct
7 Correct 72 ms 24188 KB Output is correct
8 Correct 59 ms 19576 KB Output is correct
9 Correct 77 ms 22648 KB Output is correct
10 Correct 59 ms 19576 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5120 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 8 ms 5376 KB Output is correct
4 Execution timed out 1089 ms 30712 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5120 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 8 ms 5376 KB Output is correct
4 Execution timed out 1089 ms 30712 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 22260 KB Output is correct
2 Execution timed out 1084 ms 30584 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 7 ms 5248 KB Output is correct
4 Correct 7 ms 5248 KB Output is correct
5 Correct 86 ms 19320 KB Output is correct
6 Correct 60 ms 26872 KB Output is correct
7 Correct 72 ms 24188 KB Output is correct
8 Correct 59 ms 19576 KB Output is correct
9 Correct 77 ms 22648 KB Output is correct
10 Correct 59 ms 19576 KB Output is correct
11 Correct 8 ms 5248 KB Output is correct
12 Correct 9 ms 5376 KB Output is correct
13 Correct 8 ms 5376 KB Output is correct
14 Correct 10 ms 5248 KB Output is correct
15 Correct 10 ms 5248 KB Output is correct
16 Correct 8 ms 5376 KB Output is correct
17 Correct 8 ms 5248 KB Output is correct
18 Correct 9 ms 5376 KB Output is correct
19 Correct 8 ms 5248 KB Output is correct
20 Correct 9 ms 5376 KB Output is correct

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 7 ms 5248 KB Output is correct
4 Correct 7 ms 5248 KB Output is correct
5 Correct 86 ms 19320 KB Output is correct
6 Correct 60 ms 26872 KB Output is correct
7 Correct 72 ms 24188 KB Output is correct
8 Correct 59 ms 19576 KB Output is correct
9 Correct 77 ms 22648 KB Output is correct
10 Correct 59 ms 19576 KB Output is correct
11 Correct 8 ms 5120 KB Output is correct
12 Correct 7 ms 5120 KB Output is correct
13 Correct 8 ms 5376 KB Output is correct
14 Execution timed out 1089 ms 30712 KB Time limit exceeded
15 Halted 0 ms 0 KB -