oj.uz

Submission #441189

# Submission time Handle Problem Language Result Execution time Memory
441189 2021-07-04T14:25:40 Z JovanB Election Campaign (JOI15_election_campaign) C++17
10 / 100
 166 ms 31756 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int MAXN = 100000;
const int MXLOG = 18;

vector <int> graf[MAXN+5];
int dp[MAXN+5];
int par[MAXN+5][MXLOG+1];

int tjm;

int in[MAXN+5];
int out[MAXN+5];

int bit[2*MAXN+5];
int niz[2*MAXN+5];

void upd(int x, int val){
    while(x <= 2*MAXN){
        bit[x] += val;
        x += x & -x;
    }
}

int bitget(int x){
    int res = 0;
    while(x){
        res += bit[x];
        x -= x & -x;
    }
    return res;
}

int query(int l, int r){
    return bitget(r) - bitget(l-1);
}

void dfs_calc(int v, int p){
    in[v] = ++tjm;
    par[v][0] = p;
    for(int j=1; j<=MXLOG; j++) par[v][j] = par[par[v][j-1]][j-1];
    for(auto c : graf[v]) if(c != p) dfs_calc(c, v);
    out[v] = ++tjm;
}

bool is_parent(int a, int b){
    return (a == 0) || (in[a] <= in[b] && out[b] <= out[a]);
}

int lca(int a, int b){
    if(is_parent(a, b)) return a;
    for(int j=MXLOG; j>=0; j--) if(!is_parent(par[a][j], b)) a = par[a][j];
    return par[a][0];
}

struct Option{
    int a, b, c;
};

vector <Option> options[MAXN+5];

int prvidole(int a, int b){
    for(int j=MXLOG; j>=0; j--) if(!is_parent(par[b][j], a)) b = par[b][j];
    return b;
}

void dfs_solve(int v, int p){
    for(auto c : graf[v]){
        if(c != p){
            dfs_solve(c, v);
            dp[v] += dp[c];
        }
    }
    for(auto option : options[v]){
        int a = option.a;
        int b = option.b;
        int c = option.c;
        int val = c;
        if(is_parent(b, a)) swap(a, b);
        if(a == v){
            val += query(in[v], in[b]);
        }
        else{
            val += query(in[v], in[a]);
            int k = prvidole(v, b);
            val -= dp[k];
            val += query(in[k], in[b]);
        }
        dp[v] = max(dp[v], val);
    }
    if(v != 1){
        upd(in[p], dp[v]);
        upd(in[v], -dp[v]);
        upd(out[v], dp[v]);
        upd(out[p], -dp[v]);
    }
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n;
    cin >> n;
    for(int i=1; i<n; i++){
        int a, b;
        cin >> a >> b;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }
    dfs_calc(1, 0);
    int m;
    cin >> m;
    while(m--){
        int a, b, c;
        cin >> a >> b >> c;
        options[lca(a, b)].push_back({a, b, c});
    }
    dfs_solve(1, 0);
    cout << dp[1] << "\n";
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 3 ms 5020 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 4 ms 5156 KB Output is correct
5 Incorrect 103 ms 18848 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 4 ms 5068 KB Output is correct
3 Correct 4 ms 5196 KB Output is correct
4 Correct 133 ms 31360 KB Output is correct
5 Correct 131 ms 31264 KB Output is correct
6 Correct 151 ms 31296 KB Output is correct
7 Correct 134 ms 31464 KB Output is correct
8 Correct 142 ms 31380 KB Output is correct
9 Correct 120 ms 31344 KB Output is correct
10 Correct 136 ms 31268 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 4 ms 5068 KB Output is correct
3 Correct 4 ms 5196 KB Output is correct
4 Correct 133 ms 31360 KB Output is correct
5 Correct 131 ms 31264 KB Output is correct
6 Correct 151 ms 31296 KB Output is correct
7 Correct 134 ms 31464 KB Output is correct
8 Correct 142 ms 31380 KB Output is correct
9 Correct 120 ms 31344 KB Output is correct
10 Correct 136 ms 31268 KB Output is correct
11 Correct 15 ms 6112 KB Output is correct
12 Correct 150 ms 31648 KB Output is correct
13 Correct 135 ms 31692 KB Output is correct
14 Correct 124 ms 31648 KB Output is correct
15 Correct 135 ms 31684 KB Output is correct
16 Correct 118 ms 31600 KB Output is correct
17 Correct 147 ms 31552 KB Output is correct
18 Correct 140 ms 31584 KB Output is correct
19 Correct 119 ms 31580 KB Output is correct
20 Correct 144 ms 31756 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 166 ms 21504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 3 ms 5020 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 4 ms 5156 KB Output is correct
5 Incorrect 103 ms 18848 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 3 ms 5020 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 4 ms 5156 KB Output is correct
5 Incorrect 103 ms 18848 KB Output isn't correct
6 Halted 0 ms 0 KB -