oj.uz

Submission #484208

# Submission time Handle Problem Language Result Execution time Memory
484208 2021-11-02T13:20:00 Z Mahfel Election Campaign (JOI15_election_campaign) C++17
0 / 100
 131 ms 27048 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MXN = 2e5 + 20 , LOG = 20;
vector<int> adj[MXN];
int h[MXN] , sz[MXN] , sttime[MXN] , p[LOG][MXN] , zaman;
int from[MXN] , to[MXN] , c[MXN];
ll dp[MXN] , pd[MXN];
vector<int> d[MXN];
int n,m;
struct fenwick {
    int size;
    vector<int> bit;
    fenwick() {
        size = 0;
    }
    void init(int n) {
        size = n;
        bit.assign(size , 0);
    }
    void add(int i , int k) {
        for(; i < size ; i |= (i+1)) {
            bit[i] += k;
        }
    }
    void add(int l , int r , int k) {
        add(l , k); add(r , -k);
    }
    int operator[](int i) {
        int res = 0;
        for(; i >= 0 ; i = (i&(i+1))-1) {
            res += bit[i];
        }
        return res;
    }
} f;

void prep(int v , int dad) {
    p[0][v] = (dad == -1 ? v : dad);
    h[v] = (dad == -1 ? 0 : h[dad]+1);
    sz[v] = 1;
    sttime[v] = zaman++;
    for(auto u : adj[v]) {
        if(u == dad) continue;
        prep(u , v);
        sz[v] += sz[u];
    }
}
int kth_anc(int v , int k) {
    while(k > 0) {
        int x = __builtin_ctz(k);
        v = p[x][v];
        k -= (1 << x);
    }
    return v;
}
int LCA(int v , int u) {
    if(h[v] > h[u]) swap(v , u);
    u = kth_anc(u , h[u]-h[v]);
    if(v == u) return v;
    for(int i = LOG-1 ; i >= 0 ; i--) {
        if(p[i][v] != p[i][u]) {
            v = p[i][v]; u = p[i][u];
        }
    }
    return p[0][v];
}

void DFS(int v , int dad) {
    for(auto u : adj[v]) {
        if(u == dad) continue;
        DFS(u , v); pd[v] += dp[u];
    }
    dp[v] = pd[v];
    for(auto p : d[v]) {
        if(from[p] == v) {
            dp[v] = max(dp[v] , c[p] + pd[v] + f[sttime[to[p]]]-f[sttime[v]]);
        } else if(to[p] == v) {
            dp[v] = max(dp[v] , c[p] + pd[v] + f[sttime[v]]-f[sttime[from[p]]]);
        } else {
            dp[v] = max(dp[v] , c[p] + pd[v] + f[sttime[from[p]]]-f[sttime[v]] + f[sttime[to[p]]]-f[sttime[v]]);
        }
    }
    f.add(sttime[v] , sttime[v]+sz[v] , pd[v]-dp[v]);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    cin >> n;
    for(int i = 1 ; i < n ; i++) {
        int v,u; cin >> v >> u;
        adj[v].push_back(u); adj[u].push_back(v);
    }
    prep(1 , -1);
    for(int i = 1 ; i < LOG ; i++) {
        for(int j = 1 ; j <= n ; j++) {
            p[i][j] = p[i-1][p[i-1][j]];
        }
    }

    cin >> m;
    for(int i = 0 ; i < m ; i++) {
        cin >> from[i] >> to[i] >> c[i];
        d[LCA(from[i] , to[i])].push_back(i);
    }
    f.init(n);
    DFS(1 , -1);
    cout << dp[1] << "\n";
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9804 KB Output is correct
2 Correct 5 ms 9804 KB Output is correct
3 Incorrect 5 ms 9804 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9804 KB Output is correct
2 Incorrect 5 ms 9840 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9804 KB Output is correct
2 Incorrect 5 ms 9840 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9804 KB Output is correct
2 Correct 5 ms 9804 KB Output is correct
3 Incorrect 5 ms 9804 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9804 KB Output is correct
2 Correct 5 ms 9804 KB Output is correct
3 Incorrect 5 ms 9804 KB Output isn't correct
4 Halted 0 ms 0 KB -