Submission #1248559

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248559		MMJ	Election Campaign (JOI15_election_campaign)	C++20	100 / 100	94 ms	29448 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;
 
#pragma optimize("unroll-loops,Ofast")
#pragma target("tune=native,sse4")

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<ll, ll> pll;
 
#define f first
#define s second
#define mkpr make_pair
#define pque priority_queue
#define pb push_back
#define pf push_front
#define vec vector
#define pf push_front
#define Yes cout << "Yes\n";
#define YES cout << "YES\n";
#define No cout << "No\n";
#define NO cout << "NO\n";
#define em(x) (bool)(x).empty()
#define all(x) (x).begin(), (x).end()
#define tc int tc;cin >> tc; while(tc--) 
#define cps CLOCKS_PER_SEC

const int N = 1e5 + 5, P = 1e9 + 7, LG = 23;
 
int n, m, tim, dp[N][LG], h[N], st[N], ft[N];
vector <int> a[N];
vec<pair<pii, int>> q[N];

void dfs_lca(int v, int w) {
    st[v] = tim++;
    dp[v][0] = w;
    for (int i = 0; i + 1 < LG; i++)
        dp[v][i + 1] = dp[dp[v][i]][i];
        
    for (int u: a[v])
        if (u != w)    {
            h[u] = h[v] + 1;
            dfs_lca(u, v);
        }
    ft[v] = tim;
}

int kth_par(int v, int k) {
    for (int i = 0; k >> i; i++)
        if (k >> i & 1)
            v = dp[v][i];
    return v;
}

int lca(int v, int u) {
    if (h[v] < h[u])
        swap(v, u);
    v = kth_par(v, h[v] - h[u]);
    if (u == v)
        return u;
        
    for (int i = LG - 1; i >= 0; i--)
        if (dp[v][i] != dp[u][i])
            v = dp[v][i], u = dp[u][i];
    return dp[v][0];
}

int tr[N];

int get(int i) {
    int res = 0;
    for(++i; i; i -= i&-i)
        res += tr[i];
    return res;
}
void upd(int i, int x) {
    for(++i; i<=n; i += i&-i)
        tr[i] += x;
}

int ans[N][2];
void dfs(int v, int w) {
    ans[v][0] = 0;
    ans[v][1] = -P;
    for(int u: a[v]) {
        if(u != w) {
            dfs(u, v);
            ans[v][0] += max(ans[u][0], ans[u][1]);
        }
    }
    for(auto e: q[v]) {
        ans[v][1] = max(ans[v][1], ans[v][0] + get(st[e.f.f]) + get(st[e.f.s]) + e.s);
        //cout << ans[v][0] + get(st[e.f.f]) + get(st[e.f.s]) + e.s << '\n';
    }
    upd(st[v], min(ans[v][0] - ans[v][1], 0));
    upd(ft[v], -min(ans[v][0] - ans[v][1], 0));
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 1; i < n; i++) {
        int v, u;
        cin >> v >> u;
        a[v].pb(u);
        a[u].pb(v);
    }
    dfs_lca(1, 0);
    cin >> m;
    for(int i = 0; i < m; i++) {
        int v, u, w;
        cin >> v >> u >> w;
        q[lca(v, u)].pb({{v, u}, w});
    }
    dfs(1, 0);
    cout << max(ans[1][0], ans[1][1]);
}

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