Submission #550753

#	Time	Username	Problem	Language	Result	Execution time	Memory
550753		thuanqvbn03	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	312 ms	37072 KiB

election_campaign

// Flower_On_Stone
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100005;
const int LOG = 17;

struct SegmentTree
{
private:
    int treeSize;
    vector<int> nodes;
    void initTree(int id, int low, int high)
    {
        if (low == high)
        {
            nodes[id] = 0;
            return;
        }
        int mid = (low + high) / 2;
        initTree(id * 2, low, mid);
        initTree(id * 2 + 1, mid + 1, high);
    }
    void update(int id, int low, int high, int left, int right, int val)
    {
        if (low > right || high < left)
        {
            return;
        }
        if (low >= left && high <= right)
        {
            nodes[id] += val;
            return;
        }
        int mid = (low + high) / 2;
        update(id * 2, low, mid, left, right, val);
        update(id * 2 + 1, mid + 1, high, left, right, val);
    }
    int get(int id, int low, int high, int pos)
    {
        if (low > pos || high < pos)
        {
            return 0;
        }
        if (low == high)
        {
            return nodes[id];
        }
        int mid = (low + high) / 2;
        return nodes[id] + (pos <= mid ? get(id * 2, low, mid, pos) : get(id * 2 + 1, mid + 1, high, pos));
    }

public:
    void init(int treeSize)
    {
        this->treeSize = treeSize;
        int tmp = 1;
        while (tmp < treeSize)
        {
            tmp *= 2;
        }
        nodes.resize(tmp * 2);
        initTree(1, 1, treeSize);
    }
    void update(int left, int right, int val)
    {
        update(1, 1, treeSize, left, right, val);
    }
    int get(int pos)
    {
        return get(1, 1, treeSize, pos);
    }
} smt;

struct Plan
{
    int u, v, cost;
} plans[MAX_N];
int numCity, numPLan;
vector<int> adj[MAX_N], planAt[MAX_N];
int start[MAX_N], stop[MAX_N], depth[MAX_N];
int parent[MAX_N][LOG];
int id;
int f[MAX_N], sumF[MAX_N];

void dfs(int node)
{
    for (int level = 0; level < LOG - 1; level++)
    {
        parent[node][level + 1] = parent[parent[node][level]][level];
    }
    start[node] = ++id;
    for (auto &u : adj[node])
    {
        if (u != parent[node][0])
        {
            depth[u] = depth[node] + 1;
            parent[u][0] = node;
            dfs(u);
        }
    }
    stop[node] = id;
}

int lca(int u, int v)
{
    if (depth[u] >depth[v])
    {
        swap(u, v);
    }
    for (int level = LOG - 1; level >= 0; level--)
    {
        if (depth[parent[v][level]] >= depth[u])
        {
            v = parent[v][level];
        }
    }
    if (u == v){
        return u;
    }
    for (int level = LOG - 1; level >= 0; level--)
    {
        if (parent[u][level] != parent[v][level])
        {
            u = parent[u][level];
            v = parent[v][level];
        }
    }
    return parent[u][0];
}

int jump(int node, int high)
{
    for (int level = LOG - 1; level >= 0; level--)
    {
        if (depth[parent[node][level]] >= high)
        {
            node = parent[node][level];
        }
    }
    return node;
}

void dp(int node)
{
    sumF[node] = 0;
    for (auto &u : adj[node])
    {
        if (u != parent[node][0])
        {
            dp(u);
            sumF[node] += f[u];
        }
    }
    f[node] = sumF[node];
    for (auto &index : planAt[node])
    {
        int u = plans[index].u, v = plans[index].v;
        int pu = jump(u, depth[node] + 1), pv = jump(v, depth[node] + 1);
        int tmp = sumF[node];
        if (u != node){
            tmp += smt.get(start[u]) - f[pu];
        }
        if (v != node)
        {
            tmp += smt.get(start[v]) - f[pv];
        }
        f[node] = max(f[node], tmp + plans[index].cost);
    }
    for (auto &u : adj[node])
    {
        if (u != parent[node][0])
        {
            smt.update(start[u], stop[u], sumF[node] - f[u]);
        }
    }
    smt.update(start[node], start[node], sumF[node]);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifdef Flower_On_Stone
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // Flower_On_Stone
    cin >> numCity;
    for (int i = 1; i < numCity; i++)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    cin >> numPLan;
    for (int i = 1; i <= numPLan; i++)
    {
        cin >> plans[i].u >> plans[i].v >> plans[i].cost;
    }
    depth[0] = -1;
    id = 0;
    dfs(1);
    smt.init(numCity);
    for (int i = 1; i <= numPLan; i++)
    {
        planAt[lca(plans[i].u, plans[i].v)].push_back(i);
    }
    dp(1);
    cout << f[1];
    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