oj.uz

Submission #658918

# Submission time Handle Problem Language Result Execution time Memory
658918 2022-11-15T12:36:43 Z dooompy Dynamic Diameter (CEOI19_diameter) C++17
31 / 100
 743 ms 71680 KB 
#include "bits/stdc++.h"

using namespace std;

void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}

#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif

using ll = long long;

#define int ll

struct node {
    int val, lazy;
};

struct update {
    int x, l, r, ql, qr, id, cent, edgeid;
};

struct edge {
    int to; ll cost; int id;
};

vector<update> history[100005];
vector<edge> adj[100005];
int sz[100005];
bool seen[100005];
int timer = 1;
int st[100005], en[100005];
multiset<ll> pathd[100005], total;
int ct = 0;

vector<vector<node>> tree;

ll get() {
    return *prev(total.end());
}

ll calc(multiset<ll> &cur) {
    if (cur.empty()) return 0;
    if (cur.size() == 1) return *cur.begin();

    auto itr = cur.end(); itr--;
    ll sum = *itr; itr--;
    sum += *itr;

    return sum;
}

void predfs(int node, int par = -1) {
    ct++;
    sz[node] = 1;
    for (auto nxt : adj[node]) {
        if (nxt.to == par)continue;
        if (seen[nxt.to]) continue;
        predfs(nxt.to, node);
        sz[node] += sz[nxt.to];
    }
}

int find(int node, int root, int par = -1) {

    for (auto nxt : adj[node]) {
        if (seen[nxt.to]) continue;
        if (nxt.to == par)continue;
        if (sz[nxt.to] * 2 > sz[root]) return find(nxt.to, root, node);
    }

    return node;
}

void dfs(int node, int par = -1) {
    st[node] = timer++;

    for (auto nxt : adj[node]) {
        if (seen[nxt.to] || nxt.to == par) continue;
        dfs(nxt.to, node);
    }

    en[node] = timer - 1;
}

void pushdown(int x, int l, int r, int id) {
    if (l == r) return;

    tree[id][2 * x].val += tree[id][x].lazy;
    tree[id][2 * x].lazy += tree[id][x].lazy;
    tree[id][2 * x + 1].val += tree[id][x].lazy;
    tree[id][2 * x + 1].lazy += tree[id][x].lazy;

    tree[id][x].lazy = 0;
}

void update(int x, int l, int r, int ql, int qr, int id, int cent, int v) {
    if (ql <= l && r <= qr) {
        if (x == 1) {
            pathd[cent].erase(pathd[cent].find(tree[id][x].val));
        }

        tree[id][x].val += v;
        tree[id][x].lazy += v;

        if (x == 1) {
            pathd[cent].insert(tree[id][x].val);
        }
        return;
    }

    if (l > qr || ql > r) return;

    pushdown(x, l, r, id);
    int mid = (l + r) / 2;

    update(2 * x, l, mid, ql, qr, id, cent, v);
    update(2 * x + 1, mid + 1, r, ql, qr, id, cent, v);

    if (x == 1) {
        pathd[cent].erase(pathd[cent].find(tree[id][x].val));
    }

    tree[id][x].val = max(tree[id][2 * x].val, tree[id][2 * x + 1].val);

    if (x == 1) {
        pathd[cent].insert(tree[id][x].val);
    }
}

void updateall(int node, int par, int cent) {
    for (auto nxt : adj[node]) {
        if (seen[nxt.to] || par == nxt.to) continue;

        update(1, 1, timer, st[nxt.to], en[nxt.to], tree.size() - 1, cent, nxt.cost);
        history[nxt.id].push_back({1, 1, timer, st[nxt.to], en[nxt.to], (int) tree.size() - 1, cent, nxt.id});

        updateall(nxt.to, node, cent);
    }
}

void centroid(int node) {
    ct = 0;
    predfs(node);

    if (ct == 1) {
        seen[node] = true; return;
    }
    int cent = find(node, node);

    for (auto nxt : adj[cent]) {
        if (seen[nxt.to]) continue;

        timer = 1;

        dfs(nxt.to, cent);

        tree.push_back({});
        tree.back().resize(4 * (timer + 1));
        pathd[cent].insert(0);

        update(1, 1, timer, st[nxt.to], en[nxt.to], tree.size() - 1, cent, nxt.cost);
        history[nxt.id].push_back({1, 1, timer, st[nxt.to], en[nxt.to], (int) tree.size() - 1, cent, nxt.id});

        updateall(nxt.to, cent, cent);
    }

    total.insert(calc(pathd[cent]));

    seen[cent] = true;

    for (auto nxt : adj[node]) {
        if (seen[nxt.to]) continue;
        centroid(nxt.to);
    }
}

ll edgeinfo[100005];

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("", "r", stdin);
//    freopen("", "w", stdout);
    int n, q, w; cin >> n >> q >> w;

    for (int i = 1; i <= n-1; i++) {
        int a, b; cin >> a >> b;
        ll c; cin >> c;
        adj[a].push_back({b, c, i});
        adj[b].push_back({a, c, i});
        edgeinfo[i] = c;
    }

    centroid(1);

//    cout << *prev(total.end()) << endl;

    ll last = 0;

    for (int i = 0; i < q; i++) {
        ll d, e; cin >> d >> e;
        d = (d + last) % (n - 1);
        d++;
        e = (e + last) % w;

        ll delta = e - edgeinfo[d];
        edgeinfo[d] = e;

        for (auto [x, l, r, ql, qr, id, cent, edgeid] : history[d]) {
            total.erase(total.find(calc(pathd[cent])));
            update(x, l, r, ql, qr, id, cent, delta);
            total.insert(calc(pathd[cent]));
        }

        last = get();
        cout << last << "\n";
    }
}

Subtask #1
0 / 11.0

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

Subtask #2
0 / 13.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9800 KB Output is correct
2 Correct 5 ms 9728 KB Output is correct
3 Correct 6 ms 9740 KB Output is correct
4 Correct 14 ms 9872 KB Output is correct
5 Correct 47 ms 10880 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 6 ms 9940 KB Output is correct
8 Correct 6 ms 9860 KB Output is correct
9 Correct 7 ms 9988 KB Output is correct
10 Correct 16 ms 10176 KB Output is correct
11 Correct 52 ms 11224 KB Output is correct
12 Correct 9 ms 11980 KB Output is correct
13 Correct 10 ms 11916 KB Output is correct
14 Correct 11 ms 12044 KB Output is correct
15 Correct 23 ms 12264 KB Output is correct
16 Correct 67 ms 13392 KB Output is correct
17 Correct 146 ms 54776 KB Output is correct
18 Correct 179 ms 54804 KB Output is correct
19 Correct 153 ms 55020 KB Output is correct
20 Correct 179 ms 55116 KB Output is correct
21 Correct 377 ms 56400 KB Output is correct

Subtask #4
0 / 18.0

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

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 48516 KB Output is correct
2 Correct 375 ms 49076 KB Output is correct
3 Correct 332 ms 44996 KB Output is correct
4 Correct 456 ms 52948 KB Output is correct
5 Correct 337 ms 47200 KB Output is correct
6 Correct 467 ms 63472 KB Output is correct
7 Correct 524 ms 58508 KB Output is correct
8 Correct 541 ms 58532 KB Output is correct
9 Correct 517 ms 58388 KB Output is correct
10 Correct 504 ms 58496 KB Output is correct
11 Correct 465 ms 57988 KB Output is correct
12 Correct 602 ms 68332 KB Output is correct
13 Correct 568 ms 61384 KB Output is correct
14 Correct 542 ms 61596 KB Output is correct
15 Correct 571 ms 61440 KB Output is correct
16 Correct 612 ms 61772 KB Output is correct
17 Correct 482 ms 62100 KB Output is correct
18 Correct 645 ms 71580 KB Output is correct
19 Correct 608 ms 61320 KB Output is correct
20 Correct 608 ms 61540 KB Output is correct
21 Correct 627 ms 61480 KB Output is correct
22 Correct 621 ms 61604 KB Output is correct
23 Correct 572 ms 61992 KB Output is correct
24 Correct 743 ms 71680 KB Output is correct

Subtask #6
0 / 27.0

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