oj.uz

Submission #370128

# Submission time Handle Problem Language Result Execution time Memory
370128 2021-02-23T10:51:30 Z Vladth11 Election Campaign (JOI15_election_campaign) C++14
100 / 100
 529 ms 45548 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debug_with_space(x) cerr << #x << " " << x << " "
//#include "shoes.h"

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <ll, pii> piii;
typedef tree <pii, null_type, less <pii>, rb_tree_tag, tree_order_statistics_node_update> OST;

const ll NMAX = 100001;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 316;
const ll nr_of_bits = 20;
const long double eps = 0.0000000000000001;

vector <ll> v[NMAX];
ll dp[NMAX][nr_of_bits + 1];
ll n;
ll lvl[NMAX];
pii timpi[NMAX];
ll stamp;
ll DP[NMAX];

ll aib[NMAX * 2 + 1];
void update(ll node, ll v) {
    for(ll i = node; i <= 2 * n; i += i&(-i)){
        aib[i] += v;
    }
}

ll query(ll node){
    ll v = 0;
    for(ll i = node; i > 0; i -= i&(-i)){
        v += aib[i];
    }
    return v;
}

struct queries {
    ll a, b, la, lb, val;
};

vector <queries> events[NMAX];

bool isParent(ll a, ll b) {
    return (timpi[a].first <= timpi[b].first && timpi[b].second <= timpi[a].second);
}

void DFS(ll node, ll p) {
    dp[node][0] = p;
    timpi[node].first = ++stamp;
    lvl[node] = lvl[p] + 1;
    for(auto x : v[node]) {
        if(x == p)
            continue;
        DFS(x, node);
    }
    timpi[node].second = ++stamp;
}

ll LCA(ll a, ll b) {
    if(lvl[a] > lvl[b])
        swap(a, b);
    ll r = a, pas = nr_of_bits;
    while(pas >= 0) {
        ll nxt = dp[r][pas];
        if(nxt != 0 && !isParent(nxt, b))
            r = nxt;
        pas--;
    }
    if(!isParent(r, b))
        r = dp[r][0];
    return r;
}
ll sol;

void Compute(ll node, ll p){
    ll sum = 0;
    for(auto x : v[node]){
        if(x == p)
            continue;
        Compute(x, node);
        sum += DP[x];
    }
    ll maxim = sum;
    for(auto x : events[node]){
        ll cost = sum + x.val;
        if(x.la != -1){
            ///poate facem ceva mai clean aici
            cost += (query(timpi[x.a].first) - query(timpi[node].first));
        }
        if(x.lb != -1){
            cost += (query(timpi[x.b].first) - query(timpi[node].first));
        }
        maxim = max(maxim, cost);
    }
    DP[node] = max(DP[node], maxim);
    ll val = sum - DP[node];
    update(timpi[node].first, val);
    update(timpi[node].second, -val);
}

int main() {
    ll i, j;
    cin >> n;
    for(i = 1; i < n; i++) {
        ll x, y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    DFS(1, 0);
    for(j = 1; j <= nr_of_bits; j++) {
        for(i = 1; i <= n; i++) {
            dp[i][j] = dp[dp[i][j - 1]][j - 1];
        }
    }
    ll m;
    cin >> m;
    while(m--) {
        ll a, b, la, lb, val;
        cin >> a >> b >> val;
        ll lca = LCA(a, b);
        if(lvl[a] == lvl[lca]) {
            la = -1;
        } else {
            ll r = a, pas = nr_of_bits;
            while(pas >= 0) {
                ll nxt = dp[r][pas];
                if(nxt != 0 && !isParent(nxt, lca))
                    r = nxt;
                pas--;
            }
            la = r;
        }
        if(lvl[b] == lvl[lca]) {
            lb = -1;
        } else {
            ll r = b, pas = nr_of_bits;
            while(pas >= 0) {
                ll nxt = dp[r][pas];
                if(nxt != 0 && !isParent(nxt, lca))
                    r = nxt;
                pas--;
            }
            lb = r;
        }
        events[lca].push_back({a, b, la, lb, val});
    }
    Compute(1, 0);
    cout << DP[1];
    return 0;
}

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 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5356 KB Output is correct
5 Correct 176 ms 31340 KB Output is correct
6 Correct 122 ms 38380 KB Output is correct
7 Correct 156 ms 36076 KB Output is correct
8 Correct 149 ms 31468 KB Output is correct
9 Correct 158 ms 34412 KB Output is correct
10 Correct 141 ms 31340 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 5 ms 5364 KB Output is correct
4 Correct 345 ms 42740 KB Output is correct
5 Correct 359 ms 42680 KB Output is correct
6 Correct 298 ms 42748 KB Output is correct
7 Correct 336 ms 42860 KB Output is correct
8 Correct 342 ms 42860 KB Output is correct
9 Correct 305 ms 42732 KB Output is correct
10 Correct 348 ms 42732 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 5 ms 5364 KB Output is correct
4 Correct 345 ms 42740 KB Output is correct
5 Correct 359 ms 42680 KB Output is correct
6 Correct 298 ms 42748 KB Output is correct
7 Correct 336 ms 42860 KB Output is correct
8 Correct 342 ms 42860 KB Output is correct
9 Correct 305 ms 42732 KB Output is correct
10 Correct 348 ms 42732 KB Output is correct
11 Correct 30 ms 6924 KB Output is correct
12 Correct 344 ms 42732 KB Output is correct
13 Correct 365 ms 42732 KB Output is correct
14 Correct 305 ms 42732 KB Output is correct
15 Correct 336 ms 42732 KB Output is correct
16 Correct 317 ms 42732 KB Output is correct
17 Correct 339 ms 42732 KB Output is correct
18 Correct 338 ms 42732 KB Output is correct
19 Correct 327 ms 42732 KB Output is correct
20 Correct 329 ms 42732 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 34956 KB Output is correct
2 Correct 294 ms 45164 KB Output is correct
3 Correct 529 ms 42596 KB Output is correct
4 Correct 265 ms 38136 KB Output is correct
5 Correct 411 ms 41604 KB Output is correct
6 Correct 273 ms 37976 KB Output is correct
7 Correct 453 ms 41344 KB Output is correct
8 Correct 353 ms 37632 KB Output is correct
9 Correct 314 ms 45240 KB Output is correct
10 Correct 473 ms 40316 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 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5356 KB Output is correct
5 Correct 176 ms 31340 KB Output is correct
6 Correct 122 ms 38380 KB Output is correct
7 Correct 156 ms 36076 KB Output is correct
8 Correct 149 ms 31468 KB Output is correct
9 Correct 158 ms 34412 KB Output is correct
10 Correct 141 ms 31340 KB Output is correct
11 Correct 6 ms 5356 KB Output is correct
12 Correct 6 ms 5484 KB Output is correct
13 Correct 6 ms 5356 KB Output is correct
14 Correct 5 ms 5356 KB Output is correct
15 Correct 6 ms 5356 KB Output is correct
16 Correct 6 ms 5356 KB Output is correct
17 Correct 6 ms 5356 KB Output is correct
18 Correct 8 ms 5356 KB Output is correct
19 Correct 6 ms 5356 KB Output is correct
20 Correct 6 ms 5484 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 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5356 KB Output is correct
5 Correct 176 ms 31340 KB Output is correct
6 Correct 122 ms 38380 KB Output is correct
7 Correct 156 ms 36076 KB Output is correct
8 Correct 149 ms 31468 KB Output is correct
9 Correct 158 ms 34412 KB Output is correct
10 Correct 141 ms 31340 KB Output is correct
11 Correct 4 ms 5100 KB Output is correct
12 Correct 4 ms 5100 KB Output is correct
13 Correct 5 ms 5364 KB Output is correct
14 Correct 345 ms 42740 KB Output is correct
15 Correct 359 ms 42680 KB Output is correct
16 Correct 298 ms 42748 KB Output is correct
17 Correct 336 ms 42860 KB Output is correct
18 Correct 342 ms 42860 KB Output is correct
19 Correct 305 ms 42732 KB Output is correct
20 Correct 348 ms 42732 KB Output is correct
21 Correct 30 ms 6924 KB Output is correct
22 Correct 344 ms 42732 KB Output is correct
23 Correct 365 ms 42732 KB Output is correct
24 Correct 305 ms 42732 KB Output is correct
25 Correct 336 ms 42732 KB Output is correct
26 Correct 317 ms 42732 KB Output is correct
27 Correct 339 ms 42732 KB Output is correct
28 Correct 338 ms 42732 KB Output is correct
29 Correct 327 ms 42732 KB Output is correct
30 Correct 329 ms 42732 KB Output is correct
31 Correct 326 ms 34956 KB Output is correct
32 Correct 294 ms 45164 KB Output is correct
33 Correct 529 ms 42596 KB Output is correct
34 Correct 265 ms 38136 KB Output is correct
35 Correct 411 ms 41604 KB Output is correct
36 Correct 273 ms 37976 KB Output is correct
37 Correct 453 ms 41344 KB Output is correct
38 Correct 353 ms 37632 KB Output is correct
39 Correct 314 ms 45240 KB Output is correct
40 Correct 473 ms 40316 KB Output is correct
41 Correct 6 ms 5356 KB Output is correct
42 Correct 6 ms 5484 KB Output is correct
43 Correct 6 ms 5356 KB Output is correct
44 Correct 5 ms 5356 KB Output is correct
45 Correct 6 ms 5356 KB Output is correct
46 Correct 6 ms 5356 KB Output is correct
47 Correct 6 ms 5356 KB Output is correct
48 Correct 8 ms 5356 KB Output is correct
49 Correct 6 ms 5356 KB Output is correct
50 Correct 6 ms 5484 KB Output is correct
51 Correct 351 ms 37944 KB Output is correct
52 Correct 346 ms 45420 KB Output is correct
53 Correct 494 ms 40848 KB Output is correct
54 Correct 266 ms 37912 KB Output is correct
55 Correct 339 ms 37884 KB Output is correct
56 Correct 347 ms 45456 KB Output is correct
57 Correct 449 ms 41476 KB Output is correct
58 Correct 268 ms 38008 KB Output is correct
59 Correct 365 ms 37788 KB Output is correct
60 Correct 339 ms 45420 KB Output is correct
61 Correct 472 ms 41688 KB Output is correct
62 Correct 268 ms 37304 KB Output is correct
63 Correct 361 ms 37184 KB Output is correct
64 Correct 340 ms 45548 KB Output is correct
65 Correct 503 ms 41748 KB Output is correct
66 Correct 274 ms 38064 KB Output is correct
67 Correct 368 ms 37660 KB Output is correct
68 Correct 352 ms 45440 KB Output is correct
69 Correct 431 ms 40452 KB Output is correct
70 Correct 282 ms 37236 KB Output is correct