Submission #895695

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
895695	2023-12-30T14:41:07 Z	math_rabbit_1028	Dynamic Diameter (CEOI19_diameter)	C++14	7 / 100	169 ms	29668 KB

diameter

#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];
vector<int> child[101010];
int par[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;
        ett(u, v);
    }
    out[v] = r;
}

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]]};
            tree[v].idx = ord[st];
            tree[v].val = 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);
    ett(1);
    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);
        pil y = seg.get(1, 1, n, 1, in[x.idx]-1);
        pil z = seg.get(1, 1, n, in[x.idx]+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:79:5: warning: control reaches end of non-void function [-Wreturn-type]
   79 |     }
      |     ^

Subtask #1
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	12636 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	12636 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	12632 KB	Output is correct
2	Correct	2 ms	12636 KB	Output is correct
3	Correct	3 ms	12636 KB	Output is correct
4	Correct	11 ms	12892 KB	Output is correct
5	Correct	34 ms	13928 KB	Output is correct
6	Correct	2 ms	12636 KB	Output is correct
7	Correct	2 ms	12776 KB	Output is correct
8	Correct	2 ms	12636 KB	Output is correct
9	Correct	3 ms	12636 KB	Output is correct
10	Correct	18 ms	13060 KB	Output is correct
11	Correct	67 ms	13908 KB	Output is correct
12	Correct	4 ms	15196 KB	Output is correct
13	Correct	4 ms	15192 KB	Output is correct
14	Correct	5 ms	15196 KB	Output is correct
15	Correct	16 ms	15452 KB	Output is correct
16	Correct	69 ms	16536 KB	Output is correct
17	Correct	32 ms	28108 KB	Output is correct
18	Correct	26 ms	28096 KB	Output is correct
19	Correct	28 ms	28008 KB	Output is correct
20	Correct	59 ms	28476 KB	Output is correct
21	Correct	117 ms	29668 KB	Output is correct