oj.uz

Submission #895906

# Submission time Handle Problem Language Result Execution time Memory
895906 2023-12-31T04:27:42 Z math_rabbit_1028 Dynamic Diameter (CEOI19_diameter) C++14
7 / 100
 1848 ms 1048576 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef struct {
    int idx;
    ll val;
} pil;

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

struct subtree {
    int cent, tot, r;
    vector<int> ord;
    unordered_map<int, int> in, out, depth, table[20], child;
    unordered_map<int, ll> dis;

    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;
            if (ch[u] == 1) continue;
            dis[u] = dis[v] + adj[v][i].val;
            depth[u] = depth[v] + 1;
            table[0][u] = v;
            ett(u, v);
        }
        out[v] = r;
    }

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

    struct maxseg {
        vector<pil> tree;
        vector<ll> lazy;

        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, int st, int ed) {
            tree[v].val += lazy[v];
            if (st != ed) {
                lazy[2*v] += lazy[v];
                lazy[2*v+1] += lazy[v];
            }
            lazy[v] = 0;
        }

        void init(int v, int st, int ed, vector<int>* ord, unordered_map<int, ll>* dis) {
            if (st == ed) {
                tree[v] = {(*ord)[st], (*dis)[(*ord)[st]]};
                lazy[v] = 0;
                return;
            }
            int mid = (st + ed) / 2;
            init(2*v, st, mid, ord, dis);
            init(2*v+1, mid+1, ed, ord, dis);
            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, st, ed);
            if (lt <= st && ed <= rt) {
                lazy[v] = diff;
                prop(v, st, ed);
                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, st, ed);
            if (lt <= st && ed <= rt) return tree[v];
            if (st > rt || lt > ed) return {0, 0};
            int mid = (st + ed) / 2;
            return mer(get(2*v, st, mid, lt, rt), get(2*v+1, mid+1, ed, lt, rt));
        }
    } seg;

    void init() {
        r = 0;
        for (int i = 0; i <= tot; i++) ord.push_back(0);
        seg.tree.resize(4*tot);
        seg.lazy.resize(4*tot);

        ett(cent);

        for (int k = 1; k < 20; k++) {
            for (auto iter = table[k-1].begin(); iter != table[k-1].end(); iter++) {
                table[k][iter->first] = (table[k-1][iter->second]);
            }
        }

        seg.init(1, 1, tot, &ord, &dis);
    }

    int update(int d, ll e) {
        int v = (depth[edges[d][0]] > depth[edges[d][1]] ? edges[d][0] : edges[d][1]);
        int u = (depth[edges[d][0]] < depth[edges[d][1]] ? edges[d][0] : edges[d][1]);
        seg.upd(1, 1, tot, in[v], out[v], e - edges[d][2]);
        return (u != cent ? child[get_par(v, depth[v] - 1)] : 0);
    }

    int get(ll* dst) {
        pil x = seg.get(1, 1, tot, 1, tot);
        int u = get_par(x.idx, depth[x.idx] - 1);
        pil y = seg.get(1, 1, tot, 1, in[u]-1);
        pil z = seg.get(1, 1, tot, out[u]+1, tot);
        *dst = max(*dst, x.val + max(y.val, z.val));
        return child[u];
    }

} sub[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;
}

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

    sub[v].tot = tot;
    sub[v].cent = v;
    sub[v].init();

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

    return v;
}

void update(int cent, int d, ll e) {
    while (sub[cent].tot > 1) {
        cent = sub[cent].update(d, e);
    }
}

void get(int cent, ll* dst) {
    while (sub[cent].tot > 1) {
        cent = sub[cent].get(dst);
    }
}

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});
    }

    int CENT = cent(1, n);

    ll last = 0;
    while (q--) {
        int d; ll e;
        cin >> d >> e;

        d = (d + last) % (n - 1) + 1;
        e = (e + last) % w;

        update(CENT, d, e);
        edges[d][2] = e;

        last = -1;
        get(CENT, &last);
        cout << last << "\n";

    }

    return 0;
}

Compilation message

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

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 152404 KB Output is correct
2 Correct 35 ms 152268 KB Output is correct
3 Correct 35 ms 152472 KB Output is correct
4 Correct 35 ms 152652 KB Output is correct
5 Correct 35 ms 152408 KB Output is correct
6 Correct 36 ms 152404 KB Output is correct
7 Correct 37 ms 152668 KB Output is correct
8 Correct 36 ms 152668 KB Output is correct
9 Correct 43 ms 152664 KB Output is correct
10 Correct 39 ms 152664 KB Output is correct
11 Correct 38 ms 152512 KB Output is correct
12 Correct 37 ms 152664 KB Output is correct
13 Correct 37 ms 152908 KB Output is correct
14 Incorrect 37 ms 152656 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 152404 KB Output is correct
2 Correct 35 ms 152268 KB Output is correct
3 Correct 35 ms 152472 KB Output is correct
4 Correct 35 ms 152652 KB Output is correct
5 Correct 35 ms 152408 KB Output is correct
6 Correct 36 ms 152404 KB Output is correct
7 Correct 37 ms 152668 KB Output is correct
8 Correct 36 ms 152668 KB Output is correct
9 Correct 43 ms 152664 KB Output is correct
10 Correct 39 ms 152664 KB Output is correct
11 Correct 38 ms 152512 KB Output is correct
12 Correct 37 ms 152664 KB Output is correct
13 Correct 37 ms 152908 KB Output is correct
14 Incorrect 37 ms 152656 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 152400 KB Output is correct
2 Correct 36 ms 152412 KB Output is correct
3 Correct 36 ms 152412 KB Output is correct
4 Correct 43 ms 152568 KB Output is correct
5 Correct 76 ms 152660 KB Output is correct
6 Correct 35 ms 152408 KB Output is correct
7 Correct 36 ms 153176 KB Output is correct
8 Correct 37 ms 153312 KB Output is correct
9 Correct 38 ms 153176 KB Output is correct
10 Correct 53 ms 153364 KB Output is correct
11 Correct 97 ms 153760 KB Output is correct
12 Correct 50 ms 160852 KB Output is correct
13 Correct 50 ms 161008 KB Output is correct
14 Correct 51 ms 160860 KB Output is correct
15 Correct 66 ms 161076 KB Output is correct
16 Correct 132 ms 161360 KB Output is correct
17 Correct 388 ms 337604 KB Output is correct
18 Correct 361 ms 337596 KB Output is correct
19 Correct 370 ms 337368 KB Output is correct
20 Correct 389 ms 337788 KB Output is correct
21 Correct 518 ms 338464 KB Output is correct

Subtask #4
0 / 18.0

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

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 1848 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 152404 KB Output is correct
2 Correct 35 ms 152268 KB Output is correct
3 Correct 35 ms 152472 KB Output is correct
4 Correct 35 ms 152652 KB Output is correct
5 Correct 35 ms 152408 KB Output is correct
6 Correct 36 ms 152404 KB Output is correct
7 Correct 37 ms 152668 KB Output is correct
8 Correct 36 ms 152668 KB Output is correct
9 Correct 43 ms 152664 KB Output is correct
10 Correct 39 ms 152664 KB Output is correct
11 Correct 38 ms 152512 KB Output is correct
12 Correct 37 ms 152664 KB Output is correct
13 Correct 37 ms 152908 KB Output is correct
14 Incorrect 37 ms 152656 KB Output isn't correct
15 Halted 0 ms 0 KB -