답안 #361572

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
361572	2021-01-30T15:22:51 Z	RyoPham	Election Campaign (JOI15_election_campaign)	C++14	10 / 100	309 ms	34492 KB

election_campaign

#define taskname "test"

#include <bits/stdc++.h>

using namespace std;

#define sz(x) (int)x.size()
#define fi first
#define se second

typedef long long lli;
typedef pair<int, int> pii;

const int maxn = 1e5 + 5;
const int logn = 17;

int n, m;
vector<int> gr[maxn];
int a[maxn], b[maxn], c[maxn];

int depth[maxn], p[maxn][logn];

vector<int> paths_id[maxn];

int total_child[maxn], dp[maxn];

struct fenwick
{
    int val[maxn];

    void update(int x, int k)
    {
        for(; x < maxn; x += x & -x)
            val[x] += k;
    }

    int get(int x)
    {
        int res = 0;
        for(; x > 0; x -= x & -x)
            res += val[x];
        return res;
    }

    int get(int l, int r)
    {
        return get(r) - get(l - 1);
    }
};

struct hld
{
    int sub[maxn], heavy[maxn], p[maxn];
    int nchain, ntime;
    int chain_head[maxn], chain_id[maxn], pos[maxn];
    fenwick tree;

    void dfs_pre(int u)
    {
        sub[u] = 1;
        heavy[u] = -1;
        for(auto&v: gr[u])
        {
            p[v] = u;
            dfs_pre(v);
            sub[u] += sub[v];
            if(heavy[u] == -1 || sub[v] > sub[heavy[u]])
                heavy[u] = v;
        }
    }

    void dfs_decompose(int u)
    {
        if(chain_head[nchain] == 0)
            chain_head[nchain] = u;
        chain_id[u] = nchain;
        pos[u] = ++ntime;

        if(heavy[u] != -1)
            dfs_decompose(heavy[u]);

        for(auto&v: gr[u])
            if(v != heavy[u])
            {
                ++nchain;
                dfs_decompose(v);
            }
    }

    void decompose()
    {
        dfs_pre(1);
        dfs_decompose(1);
    }

    void update(int u, int k)
    {
        if(p[u] == 0 || heavy[p[u]] == u) return;
        tree.update(pos[p[u]], k);
    }

    int get(int u, int a)
    {
        int a_chain = chain_id[a], u_chain = chain_id[u];
        int res = 0;
        if(heavy[u]) res += dp[heavy[u]];
        while(true)
        {
            if(u_chain == a_chain)
            {
                res += tree.get(pos[a], pos[u]);
                break;
            }
            res += tree.get(pos[chain_head[u_chain]], pos[u]);
            res -= dp[chain_head[u_chain]];
            res += dp[heavy[chain_head[u_chain]]];
            u = p[chain_head[u_chain]];
            u_chain = chain_id[u];
        }
        return res;
    }
} data;

void read_input()
{
    cin >> n;
    for(int i = 1; i < n; ++i)
    {
        int u, v;
        cin >> u >> v;
        gr[u].push_back(v);
        gr[v].push_back(u);
    }
    cin >> m;
    for(int i = 1; i <= m; ++i)
        cin >> a[i] >> b[i] >> c[i];
}

void dfs_modify(int u, int par)
{
    depth[u] = depth[par] + 1;
    p[u][0] = par;
    for(int k = 1; k < logn; ++k)
        p[u][k] = p[p[u][k - 1]][k - 1];
    vector<int> childs;
    for(auto&v: gr[u])
        if(v != par)
        {
            childs.push_back(v);
            dfs_modify(v, u);
        }
    gr[u] = childs;
}

int lca(int u, int v)
{
    if(depth[u] < depth[v]) swap(u, v);
    for(int k = logn - 1; k >= 0; --k)
        if(depth[p[u][k]] >= depth[v])
            u = p[u][k];
    if(u == v) return u;
    for(int k = logn - 1; k >= 0; --k)
        if(p[u][k] != p[v][k])
        {
            u = p[u][k];
            v = p[v][k];
        }
    return p[u][0];
}

int jump(int u, int dist)
{
    for(int k = 0; k < logn; ++k)
        if(dist >> k & 1) u = p[u][k];
    return u;
}

void init()
{
    dfs_modify(1, 0);
    for(int i = 1; i <= m; ++i)
        paths_id[lca(a[i], b[i])].push_back(i);
    data.decompose();
}

void dfs_solve(int u)
{
    for(auto&v: gr[u])
    {
        dfs_solve(v);
        total_child[u] += dp[v];
    }

    dp[u] = total_child[u];
    for(auto&id: paths_id[u])
    {
        int x = a[id], y = b[id], cost = c[id];
        int tx, ty;
        if(x == u)
        {
            ty = jump(y, depth[y] - depth[u] - 1);
            dp[u] = max(dp[u], data.get(y, ty) + total_child[u] - dp[ty] + cost);
        }
        else if(y == u)
        {
            tx = jump(x, depth[x] - depth[u] - 1);
            dp[u] = max(dp[u], data.get(x, tx) + total_child[u] - dp[tx] + cost);
        }
        else
        {
            tx = jump(x, depth[x] - depth[u] - 1);
            ty = jump(y, depth[y] - depth[u] - 1);
            dp[u] = max(dp[u], data.get(x, tx) + data.get(y, ty) + total_child[u] - dp[tx] - dp[ty] + cost);
        }
    }
    data.update(u, dp[u]);
}

void solve()
{
    dfs_solve(1);
    cout << dp[1] << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    read_input();
    init();
    solve();
}

Subtask #1
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	5100 KB	Output is correct
2	Correct	4 ms	5100 KB	Output is correct
3	Incorrect	4 ms	5100 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	5100 KB	Output is correct
2	Correct	4 ms	5100 KB	Output is correct
3	Correct	5 ms	5356 KB	Output is correct
4	Correct	191 ms	34152 KB	Output is correct
5	Correct	188 ms	34284 KB	Output is correct
6	Correct	167 ms	34148 KB	Output is correct
7	Correct	207 ms	34156 KB	Output is correct
8	Correct	203 ms	34284 KB	Output is correct
9	Correct	168 ms	34156 KB	Output is correct
10	Correct	183 ms	34124 KB	Output is correct

Subtask #3
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	5100 KB	Output is correct
2	Correct	4 ms	5100 KB	Output is correct
3	Correct	5 ms	5356 KB	Output is correct
4	Correct	191 ms	34152 KB	Output is correct
5	Correct	188 ms	34284 KB	Output is correct
6	Correct	167 ms	34148 KB	Output is correct
7	Correct	207 ms	34156 KB	Output is correct
8	Correct	203 ms	34284 KB	Output is correct
9	Correct	168 ms	34156 KB	Output is correct
10	Correct	183 ms	34124 KB	Output is correct
11	Correct	17 ms	6124 KB	Output is correct
12	Correct	199 ms	34412 KB	Output is correct
13	Correct	181 ms	34412 KB	Output is correct
14	Correct	171 ms	34444 KB	Output is correct
15	Correct	183 ms	34424 KB	Output is correct
16	Correct	164 ms	34492 KB	Output is correct
17	Correct	172 ms	34404 KB	Output is correct
18	Correct	190 ms	34412 KB	Output is correct
19	Correct	169 ms	34468 KB	Output is correct
20	Correct	189 ms	34416 KB	Output is correct