Submission #1248215

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248215		chikien2009	Election Campaign (JOI15_election_campaign)	C++20	100 / 100	313 ms	30320 KiB

election_campaign

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

struct SEGMENT_TREE
{
    int tree[400000];
    inline void Update(int ind, int l, int r, int x, int y, int v)
    {
        if (r < x || y < l)
        {
            return;
        }
        if (x <= l && r <= y)
        {
            tree[ind] += v;
            return;
        }
        int m = (l + r) >> 1;
        Update(ind << 1, l, m, x, y, v);
        Update(ind << 1 | 1, m + 1, r, x, y, v);
    }
    inline int Get(int ind, int l, int r, int x)
    {
        if (l == r)
        {
            return tree[ind];
        }
        tree[ind << 1] += tree[ind];
        tree[ind << 1 | 1] += tree[ind];
        tree[ind] = 0;
        int m = (l + r) >> 1;
        if (x <= m)
        {
            return Get(ind << 1, l, m, x);
        }
        return Get(ind << 1 | 1, m + 1, r, x);
    }
} st;

int n, m, x[100000], y[100000], a, b, f[100000], h[100000], v[100000];
int head[100000], tail[100000], sp[20][100000];
vector<int> g[100000], q[100000];

inline int LCA(int ina, int inb)
{
    if (head[ina] <= head[inb] && tail[inb] <= tail[ina])
    {
        return ina;
    }
    for (int i = 19, j; i >= 0; --i)
    {
        j = sp[i][ina];
        if (head[j] > head[inb] || tail[inb] > tail[j])
        {
            ina = j;
        }
    }
    return sp[0][ina];
}

inline void DFS1(int node, int par)
{
    head[node] = a++;
    sp[0][node] = par;
    for (int i = 1; i < 20; ++i)
    {
        sp[i][node] = sp[i - 1][sp[i - 1][node]];
    }
    for (auto &i : g[node])
    {
        if (i != par)
        {
            DFS1(i, node);
        }
    }
    tail[node] = a - 1;
}

inline void DFS2(int node, int par)
{
    h[node] = 0;
    for (auto &i : g[node])
    {
        if (i != par)
        {
            DFS2(i, node);
            h[node] += f[i];
        }
    }
    f[node] = h[node];
    for (auto &i : q[node])
    {
        f[node] = max(f[node], h[node] + st.Get(1, 1, n, head[x[i]]) + st.Get(1, 1, n, head[y[i]]) + v[i]);
    }
    st.Update(1, 1, n, head[node], tail[node], h[node] - f[node]);
}

int main()
{
    setup();

    cin >> n;
    for (int i = 0; i < n - 1; ++i)
    {
        cin >> a >> b;
        g[a - 1].push_back(b - 1);
        g[b - 1].push_back(a - 1);
    }
    a = 1;
    DFS1(0, 0);
    cin >> m;
    for (int i = 0; i < m; ++i)
    {
        cin >> x[i] >> y[i] >> v[i];
        x[i]--;
        y[i]--;
        a = LCA(x[i], y[i]);
        q[a].push_back(i);
    }
    DFS2(0, 0);
    cout << f[0];
    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