oj.uz

Submission #689778

# Submission time Handle Problem Language Result Execution time Memory
689778 2023-01-29T11:05:23 Z overwatch9 Dynamic Diameter (CEOI19_diameter) C++17
18 / 100
 356 ms 19404 KB 
// subtask4
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
using ll = long long;
const int MAX_N = 1e5 + 1;
vector <pair <int, ll>> adj[MAX_N];
struct edge {
    int a, b;
    ll w;
};
edge edges[MAX_N];
int parent[MAX_N];
vector <ll> seg_tree, value, diameter;
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;
        diameter[a] = max({diameter[a*2], diameter[a*2+1], seg_tree[a*2] + seg_tree[a*2+1]});
        seg_tree[a] = value[a] + max(seg_tree[a*2], seg_tree[a*2+1]);
    }
}
void dfs(int s, int p) {
    parent[s] = p;
    for (auto i : adj[s]) {
        if (i.first == p)
            continue;
        dfs(i.first, s);
    }
}
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);
    diameter.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;
        ll w = edges[i].w;
        if (parent[a] == b) {
            update(w, a);
        } else {
            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;

        if (parent[a] == b) {
            update(e, a);
        } else {
            update(e, b);
        }
        edges[d].w = e;
        last = diameter[1];
        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 2 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 2 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
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2772 KB Output is correct
2 Correct 19 ms 2832 KB Output is correct
3 Correct 90 ms 3032 KB Output is correct
4 Correct 199 ms 3236 KB Output is correct
5 Correct 12 ms 4180 KB Output is correct
6 Correct 28 ms 4444 KB Output is correct
7 Correct 101 ms 4984 KB Output is correct
8 Correct 192 ms 5788 KB Output is correct
9 Correct 51 ms 10244 KB Output is correct
10 Correct 72 ms 10376 KB Output is correct
11 Correct 148 ms 11032 KB Output is correct
12 Correct 233 ms 11956 KB Output is correct
13 Correct 98 ms 17748 KB Output is correct
14 Correct 116 ms 17956 KB Output is correct
15 Correct 210 ms 18568 KB Output is correct
16 Correct 278 ms 19404 KB Output is correct
17 Correct 280 ms 19252 KB Output is correct

Subtask #5
0 / 24.0

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

Subtask #6
0 / 27.0

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