oj.uz

Submission #370126

# Submission time Handle Problem Language Result Execution time Memory
370126 2021-02-23T10:49:06 Z Vladth11 Election Campaign (JOI15_election_campaign) C++14
10 / 100
 366 ms 45676 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);
        DP[node] = max(DP[node], DP[x]);
        sum += DP[x];
    }
    ll maxim = 0;
    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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5240 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Incorrect 4 ms 5356 KB Output isn't correct
5 Halted 0 ms 0 KB -

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 5356 KB Output is correct
4 Correct 327 ms 45164 KB Output is correct
5 Correct 328 ms 45292 KB Output is correct
6 Correct 317 ms 45368 KB Output is correct
7 Correct 330 ms 45420 KB Output is correct
8 Correct 332 ms 45148 KB Output is correct
9 Correct 292 ms 45164 KB Output is correct
10 Correct 337 ms 45292 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 5356 KB Output is correct
4 Correct 327 ms 45164 KB Output is correct
5 Correct 328 ms 45292 KB Output is correct
6 Correct 317 ms 45368 KB Output is correct
7 Correct 330 ms 45420 KB Output is correct
8 Correct 332 ms 45148 KB Output is correct
9 Correct 292 ms 45164 KB Output is correct
10 Correct 337 ms 45292 KB Output is correct
11 Correct 33 ms 7276 KB Output is correct
12 Correct 357 ms 45676 KB Output is correct
13 Correct 353 ms 45544 KB Output is correct
14 Correct 314 ms 45548 KB Output is correct
15 Correct 360 ms 45548 KB Output is correct
16 Correct 327 ms 45548 KB Output is correct
17 Correct 354 ms 45420 KB Output is correct
18 Correct 366 ms 45548 KB Output is correct
19 Correct 314 ms 45420 KB Output is correct
20 Correct 361 ms 45548 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 309 ms 34940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5240 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Incorrect 4 ms 5356 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5240 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Incorrect 4 ms 5356 KB Output isn't correct
5 Halted 0 ms 0 KB -