oj.uz

Submission #776401

# Submission time Handle Problem Language Result Execution time Memory
776401 2023-07-07T20:10:56 Z ThegeekKnight16 Election Campaign (JOI15_election_campaign) C++17
50 / 100
 269 ms 35496 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
const int MAXK = 25;
array<vector<int>, MAXN> grafo;
array<vector<tuple<int, int, int>>, MAXN> plans;
array<array<int, MAXK>, MAXN> bnLift;
array<int, MAXN> prof, sub, tin, tout, head;
array<array<int, 2>, MAXN> dp;
array<int, 4*MAXN> seg;
int temp = 0;
int N;

void update(int pos, int ini, int fim, int id, int val)
{
    if (id < ini || id > fim) return;
    if (ini == fim)
    {
        seg[pos] = val;
        return;
    }
    int m = (ini + fim) >> 1;
    int e = 2*pos; int d = 2*pos + 1;
    update(e, ini, m, id, val);
    update(d, m+1, fim, id, val);
    seg[pos] = seg[e] + seg[d];
}

int query(int pos, int ini, int fim, int p, int q)
{
    if (q < ini || p > fim) return 0;
    if (p <= ini && fim <= q) return seg[pos];
    int m = (ini + fim) >> 1;
    int e = 2*pos; int d = 2*pos + 1;
    return (query(e, ini, m, p, q) + query(d, m+1, fim, p, q));
}

void dfsProf(int v, int p)
{
    sub[v] = 1; prof[v] = prof[p] + 1;
    bnLift[v][0] = p;
    for (int k = 1; k < MAXK; k++) bnLift[v][k] = bnLift[bnLift[v][k-1]][k-1];

    for (auto &viz : grafo[v])
    {
        if (viz == p) continue;
        dfsProf(viz, v);
        sub[v] += sub[viz];
        if (grafo[v][0] == p || sub[grafo[v][0]] < sub[viz]) swap(viz, grafo[v][0]);
    }
}

void dfsInit(int v, int p, int paiCur)
{
    tin[v] = ++temp; head[v] = paiCur;

    for (auto viz : grafo[v])
    {
        if (viz == p) continue;
        if (viz == grafo[v][0]) dfsInit(viz, v, paiCur);
        else dfsInit(viz, v, viz);
    }

    tout[v] = temp;
}

//Path from x to y
int query_path(int x, int y)
{
    if (head[x] == head[y]) return query(1, 1, N, tin[y], tin[x]);
    else return (query(1, 1, N, tin[head[x]], tin[x]) + query_path(bnLift[head[x]][0], y));
}

int lca(int a, int b)
{
    if (prof[a] < prof[b]) swap(a, b);
    int jump = prof[a] - prof[b];
    for (int k = 0; k < MAXK; k++) if (jump & (1 << k)) a = bnLift[a][k];
    if (a == b) return a;
    for (int k = MAXK-1; k >= 0; k--)
        if (bnLift[a][k] != bnLift[b][k]) a = bnLift[a][k], b = bnLift[b][k];

    return bnLift[a][0];
}

void dfsDp(int v, int p)
{
    dp[v][0] = dp[v][1] = 0;

    for (auto viz : grafo[v])
    {
        if (viz == p) continue;
        dfsDp(viz, v);
        dp[v][0] += dp[viz][1];
    }

    dp[v][1] = dp[v][0];
    for (auto [X, Y, C] : plans[v])
    {
        int aux = dp[v][0];
        aux += query_path(X, v);
        aux += query_path(Y, v);
        aux += C;
        dp[v][1] = max(dp[v][1], aux);
    }

    update(1, 1, N, tin[v], dp[v][0] - dp[v][1]);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    for (int i = 1; i < N; i++)
    {
        int X, Y;
        cin >> X >> Y;
        grafo[X].push_back(Y);
        grafo[Y].push_back(X);
    }
    dfsProf(1, 1); dfsInit(1, 1, 1);
    dfsDp(1, 1);

    int M;
    cin >> M;
    for (int i = 1; i <= N; i++)
    {
        int X, Y, C;
        cin >> X >> Y >> C;
        if (prof[X] > prof[Y]) swap(X, Y);
        plans[lca(X, Y)].emplace_back(X, Y, C);
    }

    dfsDp(1, 1);

    cout << max(dp[1][0], dp[1][1]) << '\n';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5032 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 5076 KB Output is correct
4 Correct 3 ms 5204 KB Output is correct
5 Correct 183 ms 24736 KB Output is correct
6 Correct 93 ms 33880 KB Output is correct
7 Correct 129 ms 30664 KB Output is correct
8 Correct 115 ms 25044 KB Output is correct
9 Correct 148 ms 28796 KB Output is correct
10 Correct 118 ms 24976 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 2 ms 4948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 2 ms 4948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 25740 KB Output is correct
2 Correct 121 ms 35496 KB Output is correct
3 Correct 219 ms 31836 KB Output is correct
4 Correct 159 ms 26160 KB Output is correct
5 Correct 191 ms 31232 KB Output is correct
6 Correct 161 ms 26308 KB Output is correct
7 Correct 221 ms 30952 KB Output is correct
8 Correct 211 ms 26064 KB Output is correct
9 Correct 127 ms 35464 KB Output is correct
10 Correct 219 ms 29700 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5032 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 5076 KB Output is correct
4 Correct 3 ms 5204 KB Output is correct
5 Correct 183 ms 24736 KB Output is correct
6 Correct 93 ms 33880 KB Output is correct
7 Correct 129 ms 30664 KB Output is correct
8 Correct 115 ms 25044 KB Output is correct
9 Correct 148 ms 28796 KB Output is correct
10 Correct 118 ms 24976 KB Output is correct
11 Correct 4 ms 5204 KB Output is correct
12 Correct 3 ms 5332 KB Output is correct
13 Correct 3 ms 5288 KB Output is correct
14 Correct 3 ms 5204 KB Output is correct
15 Correct 3 ms 5192 KB Output is correct
16 Correct 3 ms 5204 KB Output is correct
17 Correct 3 ms 5204 KB Output is correct
18 Correct 5 ms 5308 KB Output is correct
19 Correct 3 ms 5164 KB Output is correct
20 Correct 3 ms 5332 KB Output is correct

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5032 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 5076 KB Output is correct
4 Correct 3 ms 5204 KB Output is correct
5 Correct 183 ms 24736 KB Output is correct
6 Correct 93 ms 33880 KB Output is correct
7 Correct 129 ms 30664 KB Output is correct
8 Correct 115 ms 25044 KB Output is correct
9 Correct 148 ms 28796 KB Output is correct
10 Correct 118 ms 24976 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Incorrect 2 ms 4948 KB Output isn't correct
13 Halted 0 ms 0 KB -