Submission #1162643

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162643		nhphuc	Election Campaign (JOI15_election_campaign)	C++20	50 / 100	179 ms	41696 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 100100;
const int L = 17;

int n, m, a[N], b[N], c[N], d[N], dep[N], in[N], out[N], dp[N], sum[N], t[N * 4], par[N][L], timer = 0;
vector<int> adj[N], que[N];

void upd (int id, int l, int r, int k, int x){
    if (l == r){
        t[id] += x;
        return;
    }
    int m = l + r >> 1;
    if (k <= m){
        upd(id * 2, l, m, k, x);
    } else {
        upd(id * 2 + 1, m + 1, r, k, x);
    }
    t[id] = t[id * 2] + t[id * 2 + 1];
    return;
}

int get (int id, int l, int r, int u, int v){
    if (l > v || r < u){
        return 0;
    }
    if (l >= u && r <= v){
        return t[id];
    }
    int m = l + r >> 1;
    return get(id * 2, l, m, u, v) + get(id * 2 + 1, m + 1, r, u, v);
}

void dfs (int u, int p = 0){
    dep[u] = dep[p] + 1;
    in[u] = out[u] = ++timer;
    par[u][0] = p;
    for (int i = 1; i < L; ++i){
        par[u][i] = par[par[u][i - 1]][i - 1];
    }
    for (int v : adj[u]){
        if (v != p){
            dfs(v, u);
        }
    }
    out[u] = timer;
    return;
}

int lft (int u, int x){
    for (int i = 0; i < L; ++i){
        if (x & (1 << i)){
            u = par[u][i];
        }
    }
    return u;
}

int lca (int u, int v){
    if (dep[u] < dep[v]){
        swap(u, v);
    }
    u = lft(u, dep[u] - dep[v]);
    if (u == v){
        return u;
    }
    for (int i = L - 1; i >= 0; --i){
        if (par[u][i] != par[v][i]){
            u = par[u][i];
            v = par[v][i];
        }
    }
    return par[u][0];
}

void upd (int u, int x){
    upd(1, 1, n, in[u], x);
    upd(1, 1, n, out[u] + 1, -x);
}

int get (int u){
    return get(1, 1, n, 1, in[u]);
}

void sol (int u, int p = 0){
    for (int v : adj[u]){
        if (v != p){
            sol(v, u);
            dp[u] = max(dp[u], dp[v]);
            sum[u] += dp[v];
        }
    }
    upd(u, sum[u]);
    dp[u] = max(dp[u], sum[u]);
    for (int i : que[u]){
        int road = get(a[i]) + get(b[i]) - 2 * get(d[i]) + sum[u];
        dp[u] = max(dp[u], road + c[i]);
    }
    upd(u, -dp[u]);
    return;
}

int32_t main (){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    if (fopen ("test.inp", "r")){
        freopen ("test.inp", "r", stdin);
        freopen ("test.out", "w", stdout);
    }
    cin >> n;
    for (int i = 1; i < n; ++i){
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1);
    cin >> m;
    for (int i = 1; i <= m; ++i){
        cin >> a[i] >> b[i] >> c[i];
        que[(d[i] = lca(a[i], b[i]))].push_back(i);
    }
    sol(1);
    cout << (*max_element(dp, dp + n + 1)) << "\n";
}

Compilation message (stderr)

election_campaign.cpp: In function 'int32_t main()':
election_campaign.cpp:110:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |         freopen ("test.inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp:111:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |         freopen ("test.out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 30 / 30
• Subtask 5: 0 / 10
• Subtask 6: 0 / 40