oj.uz

Submission #689764

# Submission time Handle Problem Language Result Execution time Memory
689764 2023-01-29T10:25:31 Z overwatch9 Dynamic Diameter (CEOI19_diameter) C++17
0 / 100
 401 ms 15976 KB 
// subtask4
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
using ll = long long;
const int MAX_N = 1e5 + 2;
vector <pair <int, ll>> adj[MAX_N];
struct edge {
    int a, b;
    ll w;
};
edge edges[MAX_N];
int parent[MAX_N];
int label[MAX_N];
vector <ll> seg_tree, value;
int seg_sz;
void update(ll x, int a) {
    seg_tree[a] = x;
    value[a] = x;
    for (a; a >= 1; a /= 2) {
        if (a * 2 >= seg_sz * 2)
            continue;
        seg_tree[a] = value[a] + max(seg_tree[a*2], seg_tree[a*2+1]);
    }
}
void dfs(int s, int p) {
    parent[s] = p;
    int child1 = MAX_N-1, child2 = MAX_N-1;
    for (auto i : adj[s]) {
        if (i.first == p)
            continue;
        if (child1 == MAX_N-1)
            child1 = i.first;
        else
            child2 = i.first;
        dfs(i.first, s);
    }
    if (child1 > child2)
        swap(child1, child2);
    label[child1] = s * 2;
    label[child2] = s * 2 + 1;
    if (s == 1)
        label[s] = 1;
}
int main() {
    int N, Q;
    ll W;
    cin >> N >> Q >> W;
    seg_sz = pow(2, ceil(log2(N)));
    seg_tree.resize(seg_sz * 2);
    value.resize(seg_sz * 2);
    for (int i = 0; i < N-1; i++) {
        int a, b;
        ll w;
        cin >> a >> b >> w;
        edge tp;
        tp.a = a;
        tp.b = b;
        tp.w = w;
        edges[i] = tp;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    }
    dfs(1, 1);
    for (int i = 0; i < N-1; i++) {
        int a = edges[i].a;
        int b = edges[i].b;
        a = label[a];
        b = label[b];
        ll w = edges[i].w;
        if (parent[a] == b) {
            value[a] = w;
            update(w, a);
        } else {
            value[b] = w;
            update(w, b);
        }
    }
    ll last = 0;
    while (Q--) {
        ll d, e;
        cin >> d >> e;
        d = (d + last) % (N-1);
        e = (e + last) % (W);
        int a = edges[d].a, b = edges[d].b;

        a = label[a];
        b = label[b];

        if (parent[a] == b) {
            update(e, a);
        } else {
            update(e, b);
        }
        edges[d].w = e;
        last = seg_tree[2] + seg_tree[3];
        cout << last << '\n';
    }
}

Compilation message

diameter.cpp: In function 'void update(ll, int)':
diameter.cpp:21:10: warning: statement has no effect [-Wunused-value]
   21 |     for (a; a >= 1; a /= 2) {
      |          ^

Subtask #1
0 / 11.0

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

Subtask #2
0 / 13.0

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

Subtask #3
0 / 7.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 24.0

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

Subtask #6
0 / 27.0

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