oj.uz

답안 #895909

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
895909 2023-12-31T04:33:38 Z math_rabbit_1028 Dynamic Diameter (CEOI19_diameter) C++14
31 / 100
 5000 ms 569436 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, d;
    vector<int> ord;
    map<int, int> in, out, depth, dir, child;
    map<int, ll> dis;

    void ett(int v, int par = -1) {
        ord[++r] = v; in[v] = r;
        if (par != -1) dir[v] = d;
        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;
            if (par == -1) d = u;
            ett(u, v);
        }
        out[v] = r;
    }

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

        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[dir[v]] : 0);
    }

    int get(ll* dst) {
        pil x = seg.get(1, 1, tot, 1, tot);
        int u = dir[x.idx];
        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: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:124:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pil>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |     for (int i = 0; i < adj[v].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
diameter.cpp: In function 'int get_cent(int, int, int)':
diameter.cpp:134:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pil>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |     for (int i = 0; i < adj[v].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
diameter.cpp: In function 'int cent(int, int)':
diameter.cpp:153:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pil>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |     for (int i = 0; i < adj[v].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
diameter.cpp: In member function 'pil subtree::maxseg::mer(pil, pil)':
diameter.cpp:47:9: warning: control reaches end of non-void function [-Wreturn-type]
   47 |         }
      |         ^

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 41564 KB Output is correct
2 Correct 9 ms 41564 KB Output is correct
3 Correct 8 ms 41564 KB Output is correct
4 Correct 8 ms 41672 KB Output is correct
5 Correct 8 ms 41564 KB Output is correct
6 Correct 8 ms 41600 KB Output is correct
7 Correct 8 ms 41724 KB Output is correct
8 Correct 8 ms 41564 KB Output is correct
9 Correct 8 ms 41560 KB Output is correct
10 Correct 8 ms 41560 KB Output is correct
11 Correct 8 ms 41636 KB Output is correct
12 Correct 8 ms 41564 KB Output is correct
13 Correct 9 ms 41564 KB Output is correct
14 Correct 8 ms 41584 KB Output is correct
15 Correct 8 ms 41820 KB Output is correct
16 Correct 8 ms 41820 KB Output is correct
17 Correct 8 ms 41820 KB Output is correct
18 Correct 9 ms 41820 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 41564 KB Output is correct
2 Correct 9 ms 41564 KB Output is correct
3 Correct 8 ms 41564 KB Output is correct
4 Correct 8 ms 41672 KB Output is correct
5 Correct 8 ms 41564 KB Output is correct
6 Correct 8 ms 41600 KB Output is correct
7 Correct 8 ms 41724 KB Output is correct
8 Correct 8 ms 41564 KB Output is correct
9 Correct 8 ms 41560 KB Output is correct
10 Correct 8 ms 41560 KB Output is correct
11 Correct 8 ms 41636 KB Output is correct
12 Correct 8 ms 41564 KB Output is correct
13 Correct 9 ms 41564 KB Output is correct
14 Correct 8 ms 41584 KB Output is correct
15 Correct 8 ms 41820 KB Output is correct
16 Correct 8 ms 41820 KB Output is correct
17 Correct 8 ms 41820 KB Output is correct
18 Correct 9 ms 41820 KB Output is correct
19 Correct 34 ms 43612 KB Output is correct
20 Correct 39 ms 44088 KB Output is correct
21 Correct 42 ms 44376 KB Output is correct
22 Correct 45 ms 45012 KB Output is correct
23 Correct 78 ms 53836 KB Output is correct
24 Correct 106 ms 57588 KB Output is correct
25 Correct 135 ms 59720 KB Output is correct
26 Correct 133 ms 62796 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 41564 KB Output is correct
2 Correct 8 ms 41560 KB Output is correct
3 Correct 9 ms 41564 KB Output is correct
4 Correct 16 ms 41752 KB Output is correct
5 Correct 57 ms 41948 KB Output is correct
6 Correct 9 ms 41564 KB Output is correct
7 Correct 8 ms 41816 KB Output is correct
8 Correct 8 ms 41820 KB Output is correct
9 Correct 10 ms 41820 KB Output is correct
10 Correct 26 ms 42076 KB Output is correct
11 Correct 92 ms 42324 KB Output is correct
12 Correct 16 ms 45400 KB Output is correct
13 Correct 17 ms 45400 KB Output is correct
14 Correct 21 ms 45404 KB Output is correct
15 Correct 44 ms 45496 KB Output is correct
16 Correct 149 ms 45904 KB Output is correct
17 Correct 260 ms 118632 KB Output is correct
18 Correct 250 ms 118516 KB Output is correct
19 Correct 256 ms 118612 KB Output is correct
20 Correct 305 ms 118604 KB Output is correct
21 Correct 559 ms 119056 KB Output is correct

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 44376 KB Output is correct
2 Correct 48 ms 44692 KB Output is correct
3 Correct 184 ms 45020 KB Output is correct
4 Correct 346 ms 45648 KB Output is correct
5 Correct 116 ms 82260 KB Output is correct
6 Correct 215 ms 82792 KB Output is correct
7 Correct 666 ms 83064 KB Output is correct
8 Correct 1078 ms 83600 KB Output is correct
9 Correct 690 ms 286720 KB Output is correct
10 Correct 871 ms 286672 KB Output is correct
11 Correct 1775 ms 287384 KB Output is correct
12 Correct 2840 ms 287884 KB Output is correct
13 Correct 1482 ms 567376 KB Output is correct
14 Correct 1741 ms 567612 KB Output is correct
15 Correct 2974 ms 568668 KB Output is correct
16 Correct 4382 ms 569436 KB Output is correct
17 Execution timed out 5077 ms 568880 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5033 ms 435816 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 41564 KB Output is correct
2 Correct 9 ms 41564 KB Output is correct
3 Correct 8 ms 41564 KB Output is correct
4 Correct 8 ms 41672 KB Output is correct
5 Correct 8 ms 41564 KB Output is correct
6 Correct 8 ms 41600 KB Output is correct
7 Correct 8 ms 41724 KB Output is correct
8 Correct 8 ms 41564 KB Output is correct
9 Correct 8 ms 41560 KB Output is correct
10 Correct 8 ms 41560 KB Output is correct
11 Correct 8 ms 41636 KB Output is correct
12 Correct 8 ms 41564 KB Output is correct
13 Correct 9 ms 41564 KB Output is correct
14 Correct 8 ms 41584 KB Output is correct
15 Correct 8 ms 41820 KB Output is correct
16 Correct 8 ms 41820 KB Output is correct
17 Correct 8 ms 41820 KB Output is correct
18 Correct 9 ms 41820 KB Output is correct
19 Correct 34 ms 43612 KB Output is correct
20 Correct 39 ms 44088 KB Output is correct
21 Correct 42 ms 44376 KB Output is correct
22 Correct 45 ms 45012 KB Output is correct
23 Correct 78 ms 53836 KB Output is correct
24 Correct 106 ms 57588 KB Output is correct
25 Correct 135 ms 59720 KB Output is correct
26 Correct 133 ms 62796 KB Output is correct
27 Correct 8 ms 41564 KB Output is correct
28 Correct 8 ms 41560 KB Output is correct
29 Correct 9 ms 41564 KB Output is correct
30 Correct 16 ms 41752 KB Output is correct
31 Correct 57 ms 41948 KB Output is correct
32 Correct 9 ms 41564 KB Output is correct
33 Correct 8 ms 41816 KB Output is correct
34 Correct 8 ms 41820 KB Output is correct
35 Correct 10 ms 41820 KB Output is correct
36 Correct 26 ms 42076 KB Output is correct
37 Correct 92 ms 42324 KB Output is correct
38 Correct 16 ms 45400 KB Output is correct
39 Correct 17 ms 45400 KB Output is correct
40 Correct 21 ms 45404 KB Output is correct
41 Correct 44 ms 45496 KB Output is correct
42 Correct 149 ms 45904 KB Output is correct
43 Correct 260 ms 118632 KB Output is correct
44 Correct 250 ms 118516 KB Output is correct
45 Correct 256 ms 118612 KB Output is correct
46 Correct 305 ms 118604 KB Output is correct
47 Correct 559 ms 119056 KB Output is correct
48 Correct 18 ms 44376 KB Output is correct
49 Correct 48 ms 44692 KB Output is correct
50 Correct 184 ms 45020 KB Output is correct
51 Correct 346 ms 45648 KB Output is correct
52 Correct 116 ms 82260 KB Output is correct
53 Correct 215 ms 82792 KB Output is correct
54 Correct 666 ms 83064 KB Output is correct
55 Correct 1078 ms 83600 KB Output is correct
56 Correct 690 ms 286720 KB Output is correct
57 Correct 871 ms 286672 KB Output is correct
58 Correct 1775 ms 287384 KB Output is correct
59 Correct 2840 ms 287884 KB Output is correct
60 Correct 1482 ms 567376 KB Output is correct
61 Correct 1741 ms 567612 KB Output is correct
62 Correct 2974 ms 568668 KB Output is correct
63 Correct 4382 ms 569436 KB Output is correct
64 Execution timed out 5077 ms 568880 KB Time limit exceeded
65 Halted 0 ms 0 KB -