Submission #970881

#	Time	Username	Problem	Language	Result	Execution time	Memory
970881		Beerus13	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	177 ms	29524 KiB

election_campaign

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 5;
const int K = 17;

bool maximize(auto &a, auto b) {
    if(a >= b) return true;
    a = b;
    return false;
}

int n, m, numDFS;
int dep[N], P[N][K], in[N], out[N];
ll dp[N], f[N], bit[N];
vector<int> g[N];
vector<tuple<int, int, int>> plans[N];

void update(int i, ll val) {
    for(; i <= n; i += i & -i) bit[i] += val;
}

void update(int l, int r, ll val) {
    update(l, val);
    update(r + 1, -val);
}

ll get(int i) {
    ll res = 0;
    for(; i; i -= i & -i) res += bit[i];
    return res;
}

void euler_tour(int u, int p = 0) {
    in[u] = ++numDFS;
    dep[u] = dep[p] + 1;
    P[u][0] = p;
    for(int i = 1; i < K; ++i) P[u][i] = P[P[u][i - 1]][i - 1];
    for(int v : g[u]) if(v != p) {
        euler_tour(v, u);
    }
    out[u] = numDFS;
}

int lca(int u, int v) {
    if(dep[u] < dep[v]) swap(u, v);
    for(int i = K - 1; i >= 0; --i) if(dep[P[u][i]] >= dep[v]) u = P[u][i];
    for(int i = K - 1; i >= 0; --i) if(P[u][i] != P[v][i]) u = P[u][i], v = P[v][i];
    return u == v ? u : P[u][0];
}

void dfs(int u, int p = 0) {
    for(int v : g[u]) if(v != p) dfs(v, u);
    for(auto [v1, v2, c] : plans[u]) {
        maximize(dp[u], f[u] - get(in[v1]) - get(in[v2]) + c);
    }
    maximize(dp[u], f[u]);
    update(in[u], out[u], dp[u] - f[u]);
    f[p] += dp[u];
}

void solve() {
     cin >> n;
     for(int i = 1, u, v; i < n; ++i) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
     }
     euler_tour(1);
     cin >> m;
     for(int i = 1, u, v, c; i <= m; ++i) {
        cin >> u >> v >> c;
        int p = lca(u, v);
        plans[p].emplace_back(u, v, c);
     }
     dfs(1);
     cout << dp[1] << '\n';
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int test = 1;
    // cin >> test;
    while(test--) solve();
    return 0;
}

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

Compilation message (stderr)

election_campaign.cpp:7:15: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
    7 | bool maximize(auto &a, auto b) {
      |               ^~~~
election_campaign.cpp:7:24: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
    7 | bool maximize(auto &a, auto b) {
      |                        ^~~~
election_campaign.cpp: In function 'void dfs(int, int)':
election_campaign.cpp:54:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |     for(auto [v1, v2, c] : plans[u]) {
      |              ^

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