Submission #1291524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291524		Bahamin	Election Campaign (JOI15_election_campaign)	C++20	100 / 100	291 ms	41168 KiB

election_campaign

#include <bits/stdc++.h>

using namespace std;

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }

#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#define sui cout.tie(NULL); cin.tie(NULL); ios_base::sync_with_stdio(false)
#define lid id << 1
#define rid id << 1 | 1
#define mid ((r + l) >> 1)
const int MAX_N = 1e5 + 5;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ld EPS = 1e-9;
const int LOG = 30;

vector<int> adj[MAX_N];
vector<pair<pair<int, int>, int>> al[MAX_N];
int par[MAX_N][LOG];
int st[MAX_N];
int fi[MAX_N];
int h[MAX_N];
int n;
int timer = 0;

void dfs0(int u, int p)
{
    st[u] = timer++;
    par[u][0] = p;
    for (int i = 1; i < LOG; i++) par[u][i] = par[par[u][i - 1]][i - 1];
    for (int v : adj[u]) if (v != p) h[v] = h[u] + 1, dfs0(v, u);
    fi[u] = timer;
}

int getpar(int u, int k)
{
    for (int i = 0; i < LOG; i++) if (k & (1 << i)) u = par[u][i];
    return u;
}

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

int seg[MAX_N << 2];
int ops[MAX_N << 2];

void move(int l, int r, int id)
{
    if (l == r - 1) return;
    seg[lid] += (mid - l) * ops[id];
    seg[rid] += (r - mid) * ops[id];
    ops[lid] += ops[id];
    ops[rid] += ops[id];
    ops[id] = 0;
}

void upd(int s, int t, int x, int l, int r, int id)
{
    move(l, r, id);
    if (s <= l && t >= r) 
    {
        seg[id] += (r - l) * x;
        ops[id] += x;
        return;
    }
    if (s < mid) upd(s, t, x, l, mid, lid);
    if (t > mid) upd(s, t, x, mid, r, rid);
    seg[id] = seg[lid] + seg[rid];
}

int get(int x, int l, int r, int id)
{
    move(l, r, id);
    if (l == r - 1) return seg[id];
    if (x < mid) return get(x, l, mid, lid);
    else return get(x, mid, r, rid);
}

int dp[MAX_N];

void dfs(int u, int p)
{
    dp[u] = 0;
    int sum = 0;
    vector<pair<int, int>> al1;
    al1.push_back({st[u], 0});
    for (int v : adj[u]) if (v != p) dfs(v, u), sum += dp[v], al1.push_back({st[v], dp[v]});
    sort(all(al1));
    dp[u] = sum;
    for (auto x : al[u])
    {   
        int ind1 = upper_bound(all(al1), make_pair(st[x.first.first], INF)) - al1.begin() - 1;
        int ind2 = upper_bound(all(al1), make_pair(st[x.first.second], INF)) - al1.begin() - 1;
        dp[u] = max(sum - al1[ind1].second - al1[ind2].second + get(st[x.first.first], 0, n, 1) + get(st[x.first.second], 0, n, 1) + x.second, dp[u]);
    }   
    upd(st[u], st[u] + 1, sum, 0, n, 1);
    for (int v : adj[u]) if (v != p) upd(st[v], fi[v], sum - dp[v], 0, n, 1);
}

void solve() {
    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);
    }
    dfs0(1, 0);
    int m;
    cin >> m;
    while (m--)
    {
        int u, v, c;
        cin >> u >> v >> c;
        int lc = lca(u, v);
        al[lc].push_back({{u, v}, c});
    }    
    dfs(1, 0);
    cout << dp[1] << "\n";
}

int main() {
    sui;
    int tc = 1;
    //cin >> tc;
    for (int t = 1; t <= tc; t++) {
        solve();
    }
}

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