Submission #421773

#	Time	Username	Problem	Language	Result	Execution time	Memory
421773		Hideo	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	188 ms	32332 KiB

election_campaign

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

#define all(s) s.begin(), s.end()
#define ll long long
#define fr first
#define sc second
#define pb push_back
#define mk make_pair

const int N = 1e5 + 7;
const int INF = 1e9 + 7;

ll dp[N][2];

int tin[N], tout[N], t;
int x[N], y[N], z[N];
int p[N][20];
int n, m;

int gr[N], gr_p[N], gr_l[N];
ll gr_s[N], s[N];

vector < int > g[N], q[N];

void prec (int v, int pr = 0){
    tin[v] = ++t;
    p[v][0] = pr;
    for (int j = 1; j < 20; j++)
        p[v][j] = p[p[v][j - 1]][j - 1];
    for (int to : g[v])
        if (to != pr)
            prec(to, v);
    tout[v] = t;
}

bool check (int v, int u){
    return tin[v] <= tin[u] && tout[u] <= tout[v];
}

int lca (int v, int u){
    if (check(v, u))
        return v;
    if (check(u, v))
        return u;
    for (int j = 19; j >= 0; j--)
        if (p[v][j] && !check(p[v][j], u))
            v = p[v][j];
    return p[v][0];
}

int cnt = 0;

ll get (int v, int pr){
    ll res = 0;
    while (v != pr){
        res += gr_s[gr[v]] - s[v];
        v = gr_p[gr[v]];
    }
    return res;
}

void dfs (int v){
    int mx = 0;
    for (int to : g[v]){
        if (to != p[v][0]){
            dfs(to);
            dp[v][1] += dp[to][0];
            if (mx < gr_l[gr[to]]){
                gr[v] = gr[to];
                mx = gr_l[gr[v]];
            }
        }
    }
    dp[v][0] = dp[v][1];
    for (int it : q[v]){
        dp[v][0] = max(dp[v][0], get(x[it], v) + get(y[it], v) + dp[v][1] + z[it]);
    }
    dp[v][1] -= dp[v][0];
    if (!gr[v])
        gr[v] = ++cnt;
    s[v] = gr_s[gr[v]];
    gr_s[gr[v]] += dp[v][1];
    gr_p[gr[v]] = p[v][0];
    gr_l[gr[v]]++;
}

main (){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i < n; i++){
        int a, b;
        cin >> a >> b;
        g[a].pb(b);
        g[b].pb(a);
    }
    prec(1);
    cin >> m;
    for (int i = 1; i <= m; i++){
        cin >> x[i] >> y[i] >> z[i];
        int l = lca(x[i], y[i]);
        q[l].pb(i);
    }
    dfs(1);
    cout << dp[1][0];
}

Compilation message (stderr)

election_campaign.cpp:88:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   88 | main (){
      | ^~~~

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