Submission #776403

#	Time	Username	Problem	Language	Result	Execution time	Memory
776403		ThegeekKnight16	Election Campaign (JOI15_election_campaign)	C++17	50 / 100	308 ms	46624 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
const int MAXK = 25;
#define int long long
array<vector<int>, MAXN> grafo;
array<vector<tuple<int, int, int>>, MAXN> plans;
array<array<int, MAXK>, MAXN> bnLift;
array<int, MAXN> prof, sub, tin, tout, head;
array<array<int, 2>, MAXN> dp;
array<int, 4*MAXN> seg;
int temp = 0;
int N;

void update(int pos, int ini, int fim, int id, int val)
{
    if (id < ini || id > fim) return;
    if (ini == fim)
    {
        seg[pos] = val;
        return;
    }
    int m = (ini + fim) >> 1;
    int e = 2*pos; int d = 2*pos + 1;
    update(e, ini, m, id, val);
    update(d, m+1, fim, id, val);
    seg[pos] = seg[e] + seg[d];
}

int query(int pos, int ini, int fim, int p, int q)
{
    if (q < ini || p > fim) return 0;
    if (p <= ini && fim <= q) return seg[pos];
    int m = (ini + fim) >> 1;
    int e = 2*pos; int d = 2*pos + 1;
    return (query(e, ini, m, p, q) + query(d, m+1, fim, p, q));
}

void dfsProf(int v, int p)
{
    sub[v] = 1; prof[v] = prof[p] + 1;
    bnLift[v][0] = p;
    for (int k = 1; k < MAXK; k++) bnLift[v][k] = bnLift[bnLift[v][k-1]][k-1];

    for (auto &viz : grafo[v])
    {
        if (viz == p) continue;
        dfsProf(viz, v);
        sub[v] += sub[viz];
        if (grafo[v][0] == p || sub[grafo[v][0]] < sub[viz]) swap(viz, grafo[v][0]);
    }
}

void dfsInit(int v, int p, int paiCur)
{
    tin[v] = ++temp; head[v] = paiCur;

    for (auto viz : grafo[v])
    {
        if (viz == p) continue;
        if (viz == grafo[v][0]) dfsInit(viz, v, paiCur);
        else dfsInit(viz, v, viz);
    }

    tout[v] = temp;
}

//Path from x to y
int query_path(int x, int y)
{
    if (head[x] == head[y]) return query(1, 1, N, tin[y], tin[x]);
    else return (query(1, 1, N, tin[head[x]], tin[x]) + query_path(bnLift[head[x]][0], y));
}

int lca(int a, int b)
{
    if (prof[a] < prof[b]) swap(a, b);
    int jump = prof[a] - prof[b];
    for (int k = 0; k < MAXK; k++) if (jump & (1 << k)) a = bnLift[a][k];
    if (a == b) return a;
    for (int k = MAXK-1; k >= 0; k--)
        if (bnLift[a][k] != bnLift[b][k]) a = bnLift[a][k], b = bnLift[b][k];

    return bnLift[a][0];
}

void dfsDp(int v, int p)
{
    dp[v][0] = dp[v][1] = 0;

    for (auto viz : grafo[v])
    {
        if (viz == p) continue;
        dfsDp(viz, v);
        dp[v][0] += dp[viz][1];
    }

    dp[v][1] = dp[v][0];
    for (auto [X, Y, C] : plans[v])
    {
        int aux = dp[v][0];
        aux += query_path(X, v);
        aux += query_path(Y, v);
        aux += C;
        dp[v][1] = max(dp[v][1], aux);
    }

    update(1, 1, N, tin[v], dp[v][0] - dp[v][1]);
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    for (int i = 1; i < N; i++)
    {
        int X, Y;
        cin >> X >> Y;
        grafo[X].push_back(Y);
        grafo[Y].push_back(X);
    }
    dfsProf(1, 1); dfsInit(1, 1, 1);
    dfsDp(1, 1);

    int M;
    cin >> M;
    for (int i = 1; i <= N; i++)
    {
        int X, Y, C;
        cin >> X >> Y >> C;
        if (prof[X] > prof[Y]) swap(X, Y);
        plans[lca(X, Y)].emplace_back(X, Y, C);
    }

    dfsDp(1, 1);

    cout << max(dp[1][0], dp[1][1]) << '\n';
}

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