oj.uz

Submission #895901

# Submission time Handle Problem Language Result Execution time Memory
895901 2023-12-31T04:04:45 Z math_rabbit_1028 Dynamic Diameter (CEOI19_diameter) C++14
7 / 100
 1716 ms 1048576 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];

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";

        //for (int i = 1; i < n; i++) cout << sub[CENT].seg.get(1, 1, n, i, i).val << " "; cout << "\n";
        //for (int i = 1; i < n; i++) cout << sub[CENT].seg.get(1, 1, n, i, i).idx << " "; cout << "\n";
    }

    return 0;
}

Compilation message

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

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 152404 KB Output is correct
2 Correct 35 ms 152624 KB Output is correct
3 Correct 38 ms 152260 KB Output is correct
4 Correct 35 ms 152408 KB Output is correct
5 Correct 35 ms 152408 KB Output is correct
6 Correct 36 ms 152664 KB Output is correct
7 Correct 36 ms 152524 KB Output is correct
8 Correct 35 ms 152668 KB Output is correct
9 Correct 35 ms 152616 KB Output is correct
10 Correct 36 ms 152668 KB Output is correct
11 Correct 35 ms 152540 KB Output is correct
12 Correct 35 ms 152596 KB Output is correct
13 Correct 36 ms 153176 KB Output is correct
14 Incorrect 37 ms 152920 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 152404 KB Output is correct
2 Correct 35 ms 152624 KB Output is correct
3 Correct 38 ms 152260 KB Output is correct
4 Correct 35 ms 152408 KB Output is correct
5 Correct 35 ms 152408 KB Output is correct
6 Correct 36 ms 152664 KB Output is correct
7 Correct 36 ms 152524 KB Output is correct
8 Correct 35 ms 152668 KB Output is correct
9 Correct 35 ms 152616 KB Output is correct
10 Correct 36 ms 152668 KB Output is correct
11 Correct 35 ms 152540 KB Output is correct
12 Correct 35 ms 152596 KB Output is correct
13 Correct 36 ms 153176 KB Output is correct
14 Incorrect 37 ms 152920 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 38 ms 152284 KB Output is correct
2 Correct 36 ms 152480 KB Output is correct
3 Correct 36 ms 152508 KB Output is correct
4 Correct 43 ms 152692 KB Output is correct
5 Correct 83 ms 153212 KB Output is correct
6 Correct 35 ms 152400 KB Output is correct
7 Correct 37 ms 153320 KB Output is correct
8 Correct 37 ms 153128 KB Output is correct
9 Correct 37 ms 153180 KB Output is correct
10 Correct 48 ms 153424 KB Output is correct
11 Correct 101 ms 154452 KB Output is correct
12 Correct 49 ms 160848 KB Output is correct
13 Correct 51 ms 160820 KB Output is correct
14 Correct 51 ms 160852 KB Output is correct
15 Correct 66 ms 161296 KB Output is correct
16 Correct 131 ms 162236 KB Output is correct
17 Correct 375 ms 338180 KB Output is correct
18 Correct 383 ms 338360 KB Output is correct
19 Correct 373 ms 338364 KB Output is correct
20 Correct 394 ms 338620 KB Output is correct
21 Correct 524 ms 339384 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 58 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 1716 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 34 ms 152404 KB Output is correct
2 Correct 35 ms 152624 KB Output is correct
3 Correct 38 ms 152260 KB Output is correct
4 Correct 35 ms 152408 KB Output is correct
5 Correct 35 ms 152408 KB Output is correct
6 Correct 36 ms 152664 KB Output is correct
7 Correct 36 ms 152524 KB Output is correct
8 Correct 35 ms 152668 KB Output is correct
9 Correct 35 ms 152616 KB Output is correct
10 Correct 36 ms 152668 KB Output is correct
11 Correct 35 ms 152540 KB Output is correct
12 Correct 35 ms 152596 KB Output is correct
13 Correct 36 ms 153176 KB Output is correct
14 Incorrect 37 ms 152920 KB Output isn't correct
15 Halted 0 ms 0 KB -