Submission #484486

#	Time	Username	Problem	Language	Result	Execution time	Memory
484486		Alexandruabcde	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	242 ms	31452 KiB

election_campaign

#include <bits/stdc++.h>
#define ub(x) (x&(-x))

using namespace std;

constexpr int NMAX = 1e5 + 5;
typedef pair< pair<int, int>, int> PIII;

int N;
vector <int> G[NMAX];
int Parent[20][NMAX];
int Level[NMAX];

vector <int> Euler;
int poz[NMAX];
int sz[NMAX];

vector <PIII> questions[NMAX];

int aib[NMAX];
int ans[NMAX];

int dp[NMAX];
int fara[NMAX];

void Update (int pos, int val) {
    for (int i = pos; i <= N; i += ub(i))
        aib[i] += val;
}

int Query (int pos) {
    int S = 0;
    for (int i = pos; i; i -= ub(i))
        S += aib[i];

    return S;
}

void UpdateInterval (int a, int b, int val) {
    Update(a, val);
    Update(b+1, -val);
}

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;

    for (int i = 1; i < N; ++ i ) {
        int x, y;
        cin >> x >> y;

        G[x].push_back(y);
        G[y].push_back(x);
    }
}

void Dfs (int Node, int dad = 0) {
    Parent[0][Node] = dad;
    Level[Node] = Level[dad] + 1;
    Euler.push_back(Node);
    sz[Node] = 1;
    poz[Node] = Euler.size();

    for (int lg = 1; lg < 20; ++ lg )
        Parent[lg][Node] = Parent[lg-1][Parent[lg-1][Node]];

    for (auto it : G[Node]) {
        if (it == dad) continue;

        Dfs(it, Node);
        sz[Node] += sz[it];
    }
}

int FindParent (int Node, int what) {
    for (int i = 19; i >= 0; -- i )
        if ((what & (1<<i)))
            Node = Parent[i][Node];

    return Node;
}

int Lca (int a, int b) {
    if (Level[a] < Level[b])
        swap(a, b);

    int dist = Level[a] - Level[b];
    a = FindParent(a, dist);

    if (a == b) return a;

    for (int i = 19; i >= 0; -- i )
        if (Parent[i][a] != Parent[i][b]) {
            a = Parent[i][a];
            b = Parent[i][b];
        }

    a = Parent[0][a];

    return a;
}

void ReadQueries () {
    int Q;
    cin >> Q;

    for (int i = 1; i <= Q; ++ i ) {
        int A, B, X;
        cin >> A >> B >> X;

        questions[Lca(A, B)].push_back({{A, B}, X});
    }
}

void SolveDFs (int Node, int dad = 0) {
    for (auto it : G[Node]) {
        if (it == dad) continue;

        SolveDFs(it, Node);
        fara[Node] += dp[it];
    }

    dp[Node] = fara[Node];

    for (auto q : questions[Node]) {
        int val = fara[Node] + q.second + Query(poz[q.first.first]) - Query(poz[Node]) + Query(poz[q.first.second]) - Query(poz[Node]);
        dp[Node] = max(dp[Node], val);
    }

    UpdateInterval(poz[Node], poz[Node] + sz[Node]-1, -(dp[Node] - fara[Node]));
}

int main () {
    Read();
    Dfs(1);
    ReadQueries();
    SolveDFs(1);

    cout << dp[1] << '\n';
    return 0;
}

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