oj.uz

Submission #895864

# Submission time Handle Problem Language Result Execution time Memory
895864 2023-12-31T01:27:33 Z math_rabbit_1028 Dynamic Diameter (CEOI19_diameter) C++14
31 / 100
 194 ms 48412 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef struct {
    int idx;
    ll val;
} pil;
const ll MOD = 998244353;

int n, q;
ll w;
ll edges[101010][3];
vector<pil> adj[101010];
int ch[101010], sz[101010];
int table[101010][20];
vector<int> child[101010];

void get_sz(int v, int par = -1) {
    sz[v] = 1;
    for (int i = 0; i < adj[v].size(); i++) {
        int u = adj[v][i].idx;
        if (ch[u] == 1) continue;
        if (u == par) continue;
        get_sz(u, v);
        sz[v] += sz[u];
    }
}

int get_cent(int tot, int v, int par = -1) {
    for (int i = 0; i < adj[v].size(); i++) {
        int u = adj[v][i].idx;
        if (ch[u] == 1) continue;
        if (u == par) continue;
        if (sz[u] * 2 > tot) return get_cent(tot, u, v);
    }
    return v;
}

void cent(int v, int tot) {
    get_sz(v);
    v = get_cent(tot, v);
    get_sz(v);

    ch[v] = 1;
    for (int i = 0; i < adj[v].size(); i++) {
        int u = adj[v][i].idx;
        if (ch[u] == 1) continue;
        //par[u] = v;
        child[v].push_back(u);
        cent(u, sz[u]);
    }
}

int ord[202020], r = 0, in[101010], out[101010], depth[101010];
ll dis[101010];
void ett(int v, int par = -1) {
    ord[++r] = v; in[v] = r;
    for (int i = 0; i < adj[v].size(); i++) {
        int u = adj[v][i].idx;
        if (u == par) continue;
        dis[u] = dis[v] + adj[v][i].val;
        depth[u] = depth[v] + 1;
        table[u][0] = v;
        ett(u, v);
    }
    out[v] = r;
}

void sparse() {
    for (int k = 1; k < 20; k++) {
        for (int i = 1; i <= n; i++) {
            table[i][k] = table[table[i][k-1]][k-1];
        }
    }
}

int get_par(int v, int h) {
    for (int k = 0; k < 20; k++) {
        if (h & (1<<k)) v = table[v][k];
    }
    return v;
}

struct maxseg {
    pil tree[808080];
    ll lazy[808080];

    pil mer(pil lt, pil rt) {
        if (lt.val > rt.val) return lt;
        if (lt.val < rt.val) return rt;
        if (lt.val == rt.val) {
            if (lt.idx > rt.idx) return lt;
            else return rt;
        }
    }

    void prop(int v) {
        tree[v].val += lazy[v];
        lazy[2*v] += lazy[v];
        lazy[2*v+1] += lazy[v];
        lazy[v] = 0;
    }

    void init(int v, int st, int ed) {
        if (st == ed) {
            tree[v] = {ord[st], dis[ord[st]]};
            lazy[v] = 0;
            return;
        }
        int mid = (st + ed) / 2;
        init(2*v, st, mid);
        init(2*v+1, mid+1, ed);
        tree[v] = mer(tree[2*v], tree[2*v+1]);
    }

    void upd(int v, int st, int ed, int lt, int rt, ll diff) {
        prop(v);
        if (lt <= st && ed <= rt) {
            lazy[v] = diff;
            prop(v);
            return;
        }
        if (st > rt || lt > ed) return;
        int mid = (st + ed) / 2;
        upd(2*v, st, mid, lt, rt, diff);
        upd(2*v+1, mid+1, ed, lt, rt, diff);
        tree[v] = mer(tree[2*v], tree[2*v+1]);
    }

    pil get(int v, int st, int ed, int lt, int rt) {
        prop(v);
        if (lt <= st && ed <= rt) return tree[v];
        if (st > rt || lt > ed) return {-1, -1};
        int mid = (st + ed) / 2;
        return mer(get(2*v, st, mid, lt, rt), get(2*v+1, mid+1, ed, lt, rt));
    }
} seg;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> q >> w;

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

    //cent(1, n);

    table[1][0] = 1;
    ett(1);
    sparse();
    for (int i = 1; i < n; i++) {
        if (depth[edges[i][0]] > depth[edges[i][1]]) swap(edges[i][0], edges[i][1]);
    }

    seg.init(1, 1, n);

    ll last = 0;
    while (q--) {
        int d; ll e;
        cin >> d >> e;
        d = (d + last) % (n - 1) + 1;
        e = (e + last) % w;
        int v = edges[d][1];
        seg.upd(1, 1, n, in[v], out[v], e - edges[d][2]);
        edges[d][2] = e;

        pil x = seg.get(1, 1, n, 1, n);
        int u = get_par(x.idx, depth[x.idx] - 1);
        pil y = seg.get(1, 1, n, 1, in[u]-1);
        pil z = seg.get(1, 1, n, out[u]+1, n);
        last = x.val + max(y.val, z.val);
        cout << last << "\n";
    }

    return 0;
}

Compilation message

diameter.cpp: In function 'void get_sz(int, int)':
diameter.cpp:20:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pil>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for (int i = 0; i < adj[v].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
diameter.cpp: In function 'int get_cent(int, int, int)':
diameter.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pil>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int i = 0; i < adj[v].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
diameter.cpp: In function 'void cent(int, int)':
diameter.cpp:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pil>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for (int i = 0; i < adj[v].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
diameter.cpp: In function 'void ett(int, int)':
diameter.cpp:58:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pil>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for (int i = 0; i < adj[v].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
diameter.cpp: In member function 'pil maxseg::mer(pil, pil)':
diameter.cpp:95:5: warning: control reaches end of non-void function [-Wreturn-type]
   95 |     }
      |     ^

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 14680 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 14680 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 3 ms 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 3 ms 14680 KB Output is correct
4 Correct 10 ms 14684 KB Output is correct
5 Correct 36 ms 15192 KB Output is correct
6 Correct 2 ms 14936 KB Output is correct
7 Correct 2 ms 14684 KB Output is correct
8 Correct 2 ms 14684 KB Output is correct
9 Correct 4 ms 14684 KB Output is correct
10 Correct 13 ms 14940 KB Output is correct
11 Correct 55 ms 15220 KB Output is correct
12 Correct 4 ms 17244 KB Output is correct
13 Correct 4 ms 17244 KB Output is correct
14 Correct 8 ms 17244 KB Output is correct
15 Correct 17 ms 17240 KB Output is correct
16 Correct 68 ms 17776 KB Output is correct
17 Correct 31 ms 34240 KB Output is correct
18 Correct 29 ms 34764 KB Output is correct
19 Correct 32 ms 34508 KB Output is correct
20 Correct 48 ms 34508 KB Output is correct
21 Correct 111 ms 35012 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 14684 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 147 ms 36404 KB Output is correct
2 Correct 152 ms 40568 KB Output is correct
3 Correct 142 ms 40532 KB Output is correct
4 Correct 155 ms 40532 KB Output is correct
5 Correct 148 ms 40400 KB Output is correct
6 Correct 141 ms 38196 KB Output is correct
7 Correct 152 ms 43548 KB Output is correct
8 Correct 149 ms 43604 KB Output is correct
9 Correct 162 ms 43464 KB Output is correct
10 Correct 169 ms 43540 KB Output is correct
11 Correct 147 ms 43324 KB Output is correct
12 Correct 165 ms 40492 KB Output is correct
13 Correct 135 ms 48140 KB Output is correct
14 Correct 170 ms 48412 KB Output is correct
15 Correct 194 ms 48180 KB Output is correct
16 Correct 160 ms 48208 KB Output is correct
17 Correct 173 ms 47468 KB Output is correct
18 Correct 143 ms 44228 KB Output is correct
19 Correct 138 ms 48128 KB Output is correct
20 Correct 156 ms 48304 KB Output is correct
21 Correct 168 ms 48328 KB Output is correct
22 Correct 161 ms 48212 KB Output is correct
23 Correct 158 ms 47568 KB Output is correct
24 Correct 154 ms 41972 KB Output is correct

Subtask #6
0 / 27.0

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