oj.uz

Submission #398024

# Submission time Handle Problem Language Result Execution time Memory
398024 2021-05-03T14:31:59 Z Charis02 Election Campaign (JOI15_election_campaign) C++14
20 / 100
 1000 ms 41668 KB 
/*

https://oj.uz/problem/view/JOI15_election_campaign

O(NM) Code

*/

#include<iostream>
#include<vector>
#include<string.h>
#define ll long long
#define pi pair < ll,ll >
#define mp(a,b) make_pair(a,b)
#define MAX_N 100004

using namespace std;

vector < int > graph[MAX_N];
vector < pair < pi,ll > > tours[MAX_N];
ll jump_memo[MAX_N][21];
ll tin[MAX_N],tout[MAX_N],cur_time;
ll dp[MAX_N],S[MAX_N];
int n,m;

int jump(int x,int i) // find 2^i -th ancestor of x
{
    if(jump_memo[x][i] != -1)
        return jump_memo[x][i];
    return jump_memo[x][i] = jump(jump(x,i-1),i-1);
}

bool is_ancestor(int x,int y) // returns if x is ancestor of y
{
    return (tin[x] <= tin[y] && tout[x] >= tout[y]);
}

int get_lca(int x,int y)
{
    if(is_ancestor(x,y))
        return x;
    if(is_ancestor(y,x))
        return y;

    for(int i = 20;i >= 0;i--)
    {
        if(!is_ancestor(jump(x,i),y))
            x = jump(x,i);
    }

    return jump(x,0);
}

void dfs(int cur,int par)
{
    tin[cur] = cur_time++;
    jump_memo[cur][0] = par;

    for(int i = 0;i < graph[cur].size();i++)
    {
        int v = graph[cur][i];
        if(v == par)
            continue;
        dfs(v,cur);
    }

    tout[cur] = cur_time++;
    return;
}

void initialize()
{
    memset(jump_memo,-1,sizeof jump_memo);
    memset(dp,-1,sizeof dp);
    dfs(1,1);

    return;
}

void input()
{
    int a,b,c;

    cin >> n;

    for(int i = 0;i < n-1;i++)
    {
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    initialize();
    cin >> m;

    for(int i = 0;i < m;i++)
    {
        cin >> a >> b >> c;
        tours[get_lca(a,b)].push_back(mp(mp(a,b),c));
    }

    return;
}

ll go(int cur,int par,int target)
{
    if(cur == target)
        return S[cur];
    for(int i = 0;i < graph[cur].size();i++)
    {
        int v = graph[cur][i];
        if(is_ancestor(v,target) && is_ancestor(cur,v))
            return go(v,cur,target)+S[cur]-dp[v];
    }
}

ll calc(int cur,int par)
{
    if(dp[cur] != -1)
        return dp[cur];

    for(int i = 0;i < graph[cur].size();i++)
    {
        int v = graph[cur][i];
        if(v==par)
            continue;

        S[cur] += calc(v,cur);
    }

    dp[cur] = S[cur];

    for(int i = 0;i < tours[cur].size();i++)
    {
        int x = tours[cur][i].first.first;
        int y = tours[cur][i].first.second;
        int C = tours[cur][i].second;

//        cout << "testing route " << x << " -> " << y << ".  lca is " << cur << ". Gain is " << C << ". ";
//        cout << "to x: " << go(cur,par,x) << " to y: " << go(cur,par,y) << "  S: " << S[cur] << " " << go(cur,par,x)+go(cur,par,y) - S[cur] + C << endl;

        dp[cur] = max(dp[cur],go(cur,par,x)+go(cur,par,y) - S[cur] + C); // S[cur] is counted twice
    }

  //  cout << "here " << cur << " " << dp[cur] << endl;
    return dp[cur];
}

void solve()
{
    cout << calc(1,1) << endl;
}

int main()
{
    input();
    solve();

    return 0;
}

Compilation message

election_campaign.cpp: In function 'void dfs(int, int)':
election_campaign.cpp:59:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int i = 0;i < graph[cur].size();i++)
      |                   ~~^~~~~~~~~~~~~~~~~~~
election_campaign.cpp: In function 'long long int go(int, int, int)':
election_campaign.cpp:109:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     for(int i = 0;i < graph[cur].size();i++)
      |                   ~~^~~~~~~~~~~~~~~~~~~
election_campaign.cpp: In function 'long long int calc(int, int)':
election_campaign.cpp:122:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |     for(int i = 0;i < graph[cur].size();i++)
      |                   ~~^~~~~~~~~~~~~~~~~~~
election_campaign.cpp:133:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |     for(int i = 0;i < tours[cur].size();i++)
      |                   ~~^~~~~~~~~~~~~~~~~~~
election_campaign.cpp: In function 'long long int go(int, int, int)':
election_campaign.cpp:115:1: warning: control reaches end of non-void function [-Wreturn-type]
  115 | }
      | ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 22220 KB Output is correct
2 Correct 12 ms 22124 KB Output is correct
3 Correct 13 ms 22220 KB Output is correct
4 Correct 13 ms 22288 KB Output is correct
5 Correct 138 ms 28888 KB Output is correct
6 Correct 94 ms 36548 KB Output is correct
7 Correct 129 ms 33916 KB Output is correct
8 Correct 111 ms 28612 KB Output is correct
9 Correct 150 ms 32388 KB Output is correct
10 Correct 119 ms 28576 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 22168 KB Output is correct
2 Correct 14 ms 22152 KB Output is correct
3 Correct 14 ms 22292 KB Output is correct
4 Execution timed out 1071 ms 41336 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 22168 KB Output is correct
2 Correct 14 ms 22152 KB Output is correct
3 Correct 14 ms 22292 KB Output is correct
4 Execution timed out 1071 ms 41336 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 440 ms 33156 KB Output is correct
2 Execution timed out 1090 ms 41668 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 22220 KB Output is correct
2 Correct 12 ms 22124 KB Output is correct
3 Correct 13 ms 22220 KB Output is correct
4 Correct 13 ms 22288 KB Output is correct
5 Correct 138 ms 28888 KB Output is correct
6 Correct 94 ms 36548 KB Output is correct
7 Correct 129 ms 33916 KB Output is correct
8 Correct 111 ms 28612 KB Output is correct
9 Correct 150 ms 32388 KB Output is correct
10 Correct 119 ms 28576 KB Output is correct
11 Correct 14 ms 22352 KB Output is correct
12 Correct 17 ms 22420 KB Output is correct
13 Correct 15 ms 22292 KB Output is correct
14 Correct 14 ms 22348 KB Output is correct
15 Correct 14 ms 22348 KB Output is correct
16 Correct 15 ms 22348 KB Output is correct
17 Correct 14 ms 22348 KB Output is correct
18 Correct 18 ms 22348 KB Output is correct
19 Correct 13 ms 22348 KB Output is correct
20 Correct 16 ms 22348 KB Output is correct

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 22220 KB Output is correct
2 Correct 12 ms 22124 KB Output is correct
3 Correct 13 ms 22220 KB Output is correct
4 Correct 13 ms 22288 KB Output is correct
5 Correct 138 ms 28888 KB Output is correct
6 Correct 94 ms 36548 KB Output is correct
7 Correct 129 ms 33916 KB Output is correct
8 Correct 111 ms 28612 KB Output is correct
9 Correct 150 ms 32388 KB Output is correct
10 Correct 119 ms 28576 KB Output is correct
11 Correct 12 ms 22168 KB Output is correct
12 Correct 14 ms 22152 KB Output is correct
13 Correct 14 ms 22292 KB Output is correct
14 Execution timed out 1071 ms 41336 KB Time limit exceeded
15 Halted 0 ms 0 KB -