oj.uz

Submission #361576

# Submission time Handle Problem Language Result Execution time Memory
361576 2021-01-30T15:37:56 Z RyoPham Election Campaign (JOI15_election_campaign) C++14
100 / 100
 373 ms 34520 KB 
#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[p[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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5248 KB Output is correct
3 Correct 3 ms 5100 KB Output is correct
4 Correct 4 ms 5228 KB Output is correct
5 Correct 119 ms 19948 KB Output is correct
6 Correct 71 ms 31596 KB Output is correct
7 Correct 140 ms 27628 KB Output is correct
8 Correct 90 ms 19948 KB Output is correct
9 Correct 126 ms 25256 KB Output is correct
10 Correct 80 ms 19820 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5356 KB Output is correct
4 Correct 178 ms 31724 KB Output is correct
5 Correct 156 ms 31724 KB Output is correct
6 Correct 154 ms 31724 KB Output is correct
7 Correct 167 ms 31744 KB Output is correct
8 Correct 198 ms 31724 KB Output is correct
9 Correct 149 ms 31724 KB Output is correct
10 Correct 160 ms 31724 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5356 KB Output is correct
4 Correct 178 ms 31724 KB Output is correct
5 Correct 156 ms 31724 KB Output is correct
6 Correct 154 ms 31724 KB Output is correct
7 Correct 167 ms 31744 KB Output is correct
8 Correct 198 ms 31724 KB Output is correct
9 Correct 149 ms 31724 KB Output is correct
10 Correct 160 ms 31724 KB Output is correct
11 Correct 17 ms 5868 KB Output is correct
12 Correct 196 ms 31724 KB Output is correct
13 Correct 160 ms 31724 KB Output is correct
14 Correct 152 ms 31852 KB Output is correct
15 Correct 173 ms 31852 KB Output is correct
16 Correct 150 ms 31724 KB Output is correct
17 Correct 168 ms 31980 KB Output is correct
18 Correct 184 ms 31724 KB Output is correct
19 Correct 147 ms 31724 KB Output is correct
20 Correct 167 ms 31724 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 20404 KB Output is correct
2 Correct 153 ms 34156 KB Output is correct
3 Correct 342 ms 29732 KB Output is correct
4 Correct 163 ms 23016 KB Output is correct
5 Correct 284 ms 28908 KB Output is correct
6 Correct 167 ms 22760 KB Output is correct
7 Correct 359 ms 28780 KB Output is correct
8 Correct 235 ms 23276 KB Output is correct
9 Correct 155 ms 34156 KB Output is correct
10 Correct 373 ms 27392 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5248 KB Output is correct
3 Correct 3 ms 5100 KB Output is correct
4 Correct 4 ms 5228 KB Output is correct
5 Correct 119 ms 19948 KB Output is correct
6 Correct 71 ms 31596 KB Output is correct
7 Correct 140 ms 27628 KB Output is correct
8 Correct 90 ms 19948 KB Output is correct
9 Correct 126 ms 25256 KB Output is correct
10 Correct 80 ms 19820 KB Output is correct
11 Correct 5 ms 5356 KB Output is correct
12 Correct 5 ms 5356 KB Output is correct
13 Correct 5 ms 5356 KB Output is correct
14 Correct 5 ms 5356 KB Output is correct
15 Correct 5 ms 5356 KB Output is correct
16 Correct 5 ms 5356 KB Output is correct
17 Correct 5 ms 5356 KB Output is correct
18 Correct 5 ms 5356 KB Output is correct
19 Correct 5 ms 5356 KB Output is correct
20 Correct 5 ms 5356 KB Output is correct

Subtask #6
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5248 KB Output is correct
3 Correct 3 ms 5100 KB Output is correct
4 Correct 4 ms 5228 KB Output is correct
5 Correct 119 ms 19948 KB Output is correct
6 Correct 71 ms 31596 KB Output is correct
7 Correct 140 ms 27628 KB Output is correct
8 Correct 90 ms 19948 KB Output is correct
9 Correct 126 ms 25256 KB Output is correct
10 Correct 80 ms 19820 KB Output is correct
11 Correct 4 ms 5100 KB Output is correct
12 Correct 4 ms 5100 KB Output is correct
13 Correct 4 ms 5356 KB Output is correct
14 Correct 178 ms 31724 KB Output is correct
15 Correct 156 ms 31724 KB Output is correct
16 Correct 154 ms 31724 KB Output is correct
17 Correct 167 ms 31744 KB Output is correct
18 Correct 198 ms 31724 KB Output is correct
19 Correct 149 ms 31724 KB Output is correct
20 Correct 160 ms 31724 KB Output is correct
21 Correct 17 ms 5868 KB Output is correct
22 Correct 196 ms 31724 KB Output is correct
23 Correct 160 ms 31724 KB Output is correct
24 Correct 152 ms 31852 KB Output is correct
25 Correct 173 ms 31852 KB Output is correct
26 Correct 150 ms 31724 KB Output is correct
27 Correct 168 ms 31980 KB Output is correct
28 Correct 184 ms 31724 KB Output is correct
29 Correct 147 ms 31724 KB Output is correct
30 Correct 167 ms 31724 KB Output is correct
31 Correct 300 ms 20404 KB Output is correct
32 Correct 153 ms 34156 KB Output is correct
33 Correct 342 ms 29732 KB Output is correct
34 Correct 163 ms 23016 KB Output is correct
35 Correct 284 ms 28908 KB Output is correct
36 Correct 167 ms 22760 KB Output is correct
37 Correct 359 ms 28780 KB Output is correct
38 Correct 235 ms 23276 KB Output is correct
39 Correct 155 ms 34156 KB Output is correct
40 Correct 373 ms 27392 KB Output is correct
41 Correct 5 ms 5356 KB Output is correct
42 Correct 5 ms 5356 KB Output is correct
43 Correct 5 ms 5356 KB Output is correct
44 Correct 5 ms 5356 KB Output is correct
45 Correct 5 ms 5356 KB Output is correct
46 Correct 5 ms 5356 KB Output is correct
47 Correct 5 ms 5356 KB Output is correct
48 Correct 5 ms 5356 KB Output is correct
49 Correct 5 ms 5356 KB Output is correct
50 Correct 5 ms 5356 KB Output is correct
51 Correct 259 ms 23660 KB Output is correct
52 Correct 187 ms 34520 KB Output is correct
53 Correct 346 ms 27884 KB Output is correct
54 Correct 153 ms 23148 KB Output is correct
55 Correct 282 ms 23144 KB Output is correct
56 Correct 172 ms 34432 KB Output is correct
57 Correct 296 ms 28652 KB Output is correct
58 Correct 158 ms 23020 KB Output is correct
59 Correct 263 ms 23532 KB Output is correct
60 Correct 164 ms 34412 KB Output is correct
61 Correct 326 ms 28652 KB Output is correct
62 Correct 160 ms 22956 KB Output is correct
63 Correct 312 ms 23224 KB Output is correct
64 Correct 175 ms 34412 KB Output is correct
65 Correct 350 ms 28908 KB Output is correct
66 Correct 158 ms 23148 KB Output is correct
67 Correct 301 ms 23396 KB Output is correct
68 Correct 165 ms 34412 KB Output is correct
69 Correct 287 ms 26732 KB Output is correct
70 Correct 178 ms 23148 KB Output is correct