oj.uz

Submission #329204

# Submission time Handle Problem Language Result Execution time Memory
329204 2020-11-19T18:16:41 Z Mahdi_Shokoufi Dynamic Diameter (CEOI19_diameter) C++17
100 / 100
 477 ms 63940 KB 
//In The Name of Allah
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair < int , int > pii;
typedef pair < ll , ll > pll;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x.size())
#define lc (2 * id)
#define rc (2 * id + 1)

const int N = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll inf = 1e18 + 10;

struct node{
    ll a, b, ab, ba, res, lzy;
    node(){
        a = b = ab = ba = -inf;
        res = lzy = 0;
    }
};

ll a[2 * N], st[N], ft[N], H[N], T;
vector < pll > adj[N];
pair < pll , ll > E[N];
node seg[8 * N];

void dfs(ll v, ll p){
    st[v] = T ++;
    a[st[v]] = v;
    for (pll e : adj[v]){
        ll u = e.X, w = e.Y;
        if (u == p)
            continue;
        H[u] = H[v] + w;
        dfs(u, v);
        a[T ++] = v;
    }
    ft[v] = T;
}

node merge(node A, node B){
    node C;
    C.a = max(A.a, B.a);
    C.b = max(A.b, B.b);
    C.ab = max({A.ab, B.ab, A.a + B.b});
    C.ba = max({A.ba, B.ba, A.b + B.a});
    C.res = max({A.res, B.res, A.a + B.ba, A.ab + B.a});
    C.lzy = 0;
    return C;
}

void build(int l = 0, int r = T, int id = 1){
    if (r - l == 1){
        seg[id].a = H[a[l]];
        seg[id].b = -2LL * H[a[l]];
        seg[id].ab = seg[id].ba = -H[a[l]];
        return ;
    }
    int mid = (l + r) / 2;
    build(l, mid, lc);
    build(mid, r, rc);
    seg[id] = merge(seg[lc], seg[rc]);
}

void add(int id, ll x){
    seg[id].a += x;
    seg[id].b += -2LL * x;
    seg[id].ab += -x;
    seg[id].ba += -x;
    seg[id].lzy += x;
}

void shift(int id){
    ll x = seg[id].lzy;
    if (x == 0)
        return ;
    add(lc, x);
    add(rc, x);
    seg[id].lzy = 0;
}

void upd(int l, int r, ll x, int s = 0, int e = T, int id = 1){
    if (e <= l || r <= s)
        return ;
    if (l <= s && e <= r){
        add(id, x);
        return ;
    }
    shift(id);
    int mid = (s + e) / 2;
    upd(l, r, x, s, mid, lc);
    upd(l, r, x, mid, e, rc);
    seg[id] = merge(seg[lc], seg[rc]);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n, q, W;
    cin >> n >> q >> W;
    for (int i = 1; i < n; i ++){
        ll u, v, w;
        cin >> u >> v >> w;
        adj[u].pb(mp(v, w));
        adj[v].pb(mp(u, w));
        E[i] = mp(mp(u, v), w);
    }
    dfs(1, 0);
    build();
    ll last = 0;
    while (q --){
        ll x, y;
        cin >> x >> y;
        x = (x + last) % (n - 1) + 1;
        y = (y + last) % W;
        ll v = (H[E[x].X.X] < H[E[x].X.Y] ? E[x].X.Y : E[x].X.X);
        upd(st[v], ft[v], y - E[x].Y);
        E[x].Y = y;
        last = seg[1].res;
        cout << last << '\n';
    }
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 40300 KB Output is correct
2 Correct 22 ms 40300 KB Output is correct
3 Correct 22 ms 40300 KB Output is correct
4 Correct 22 ms 40300 KB Output is correct
5 Correct 23 ms 40300 KB Output is correct
6 Correct 21 ms 40320 KB Output is correct
7 Correct 22 ms 40300 KB Output is correct
8 Correct 23 ms 40300 KB Output is correct
9 Correct 23 ms 40428 KB Output is correct
10 Correct 22 ms 40428 KB Output is correct
11 Correct 22 ms 40300 KB Output is correct
12 Correct 22 ms 40320 KB Output is correct
13 Correct 25 ms 40300 KB Output is correct
14 Correct 22 ms 40300 KB Output is correct
15 Correct 22 ms 40428 KB Output is correct
16 Correct 22 ms 40300 KB Output is correct
17 Correct 22 ms 40300 KB Output is correct
18 Correct 22 ms 40300 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 40300 KB Output is correct
2 Correct 22 ms 40300 KB Output is correct
3 Correct 22 ms 40300 KB Output is correct
4 Correct 22 ms 40300 KB Output is correct
5 Correct 23 ms 40300 KB Output is correct
6 Correct 21 ms 40320 KB Output is correct
7 Correct 22 ms 40300 KB Output is correct
8 Correct 23 ms 40300 KB Output is correct
9 Correct 23 ms 40428 KB Output is correct
10 Correct 22 ms 40428 KB Output is correct
11 Correct 22 ms 40300 KB Output is correct
12 Correct 22 ms 40320 KB Output is correct
13 Correct 25 ms 40300 KB Output is correct
14 Correct 22 ms 40300 KB Output is correct
15 Correct 22 ms 40428 KB Output is correct
16 Correct 22 ms 40300 KB Output is correct
17 Correct 22 ms 40300 KB Output is correct
18 Correct 22 ms 40300 KB Output is correct
19 Correct 27 ms 40560 KB Output is correct
20 Correct 28 ms 40556 KB Output is correct
21 Correct 32 ms 40576 KB Output is correct
22 Correct 28 ms 40556 KB Output is correct
23 Correct 33 ms 41068 KB Output is correct
24 Correct 38 ms 41068 KB Output is correct
25 Correct 33 ms 41068 KB Output is correct
26 Correct 34 ms 41324 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 40300 KB Output is correct
2 Correct 21 ms 40300 KB Output is correct
3 Correct 24 ms 40300 KB Output is correct
4 Correct 33 ms 40556 KB Output is correct
5 Correct 80 ms 41452 KB Output is correct
6 Correct 23 ms 40448 KB Output is correct
7 Correct 22 ms 40300 KB Output is correct
8 Correct 22 ms 40300 KB Output is correct
9 Correct 24 ms 40428 KB Output is correct
10 Correct 37 ms 40684 KB Output is correct
11 Correct 103 ms 41708 KB Output is correct
12 Correct 24 ms 40940 KB Output is correct
13 Correct 25 ms 40972 KB Output is correct
14 Correct 26 ms 40940 KB Output is correct
15 Correct 43 ms 41196 KB Output is correct
16 Correct 124 ms 42348 KB Output is correct
17 Correct 66 ms 52444 KB Output is correct
18 Correct 66 ms 52444 KB Output is correct
19 Correct 81 ms 52444 KB Output is correct
20 Correct 94 ms 52828 KB Output is correct
21 Correct 268 ms 54108 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 40428 KB Output is correct
2 Correct 39 ms 40556 KB Output is correct
3 Correct 79 ms 41196 KB Output is correct
4 Correct 128 ms 41836 KB Output is correct
5 Correct 29 ms 41708 KB Output is correct
6 Correct 49 ms 41708 KB Output is correct
7 Correct 127 ms 42348 KB Output is correct
8 Correct 198 ms 43244 KB Output is correct
9 Correct 50 ms 46956 KB Output is correct
10 Correct 66 ms 47228 KB Output is correct
11 Correct 159 ms 47724 KB Output is correct
12 Correct 239 ms 48620 KB Output is correct
13 Correct 77 ms 53612 KB Output is correct
14 Correct 112 ms 53740 KB Output is correct
15 Correct 219 ms 54380 KB Output is correct
16 Correct 293 ms 55532 KB Output is correct
17 Correct 288 ms 55020 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 57504 KB Output is correct
2 Correct 400 ms 57452 KB Output is correct
3 Correct 367 ms 57536 KB Output is correct
4 Correct 374 ms 57452 KB Output is correct
5 Correct 360 ms 57448 KB Output is correct
6 Correct 339 ms 57312 KB Output is correct
7 Correct 451 ms 60012 KB Output is correct
8 Correct 407 ms 60056 KB Output is correct
9 Correct 406 ms 59884 KB Output is correct
10 Correct 423 ms 60012 KB Output is correct
11 Correct 414 ms 59728 KB Output is correct
12 Correct 370 ms 59232 KB Output is correct
13 Correct 475 ms 63724 KB Output is correct
14 Correct 477 ms 63724 KB Output is correct
15 Correct 463 ms 63724 KB Output is correct
16 Correct 475 ms 63596 KB Output is correct
17 Correct 453 ms 62952 KB Output is correct
18 Correct 405 ms 60256 KB Output is correct
19 Correct 458 ms 63940 KB Output is correct
20 Correct 468 ms 63724 KB Output is correct
21 Correct 449 ms 63852 KB Output is correct
22 Correct 453 ms 63724 KB Output is correct
23 Correct 470 ms 63080 KB Output is correct
24 Correct 426 ms 60256 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 40300 KB Output is correct
2 Correct 22 ms 40300 KB Output is correct
3 Correct 22 ms 40300 KB Output is correct
4 Correct 22 ms 40300 KB Output is correct
5 Correct 23 ms 40300 KB Output is correct
6 Correct 21 ms 40320 KB Output is correct
7 Correct 22 ms 40300 KB Output is correct
8 Correct 23 ms 40300 KB Output is correct
9 Correct 23 ms 40428 KB Output is correct
10 Correct 22 ms 40428 KB Output is correct
11 Correct 22 ms 40300 KB Output is correct
12 Correct 22 ms 40320 KB Output is correct
13 Correct 25 ms 40300 KB Output is correct
14 Correct 22 ms 40300 KB Output is correct
15 Correct 22 ms 40428 KB Output is correct
16 Correct 22 ms 40300 KB Output is correct
17 Correct 22 ms 40300 KB Output is correct
18 Correct 22 ms 40300 KB Output is correct
19 Correct 27 ms 40560 KB Output is correct
20 Correct 28 ms 40556 KB Output is correct
21 Correct 32 ms 40576 KB Output is correct
22 Correct 28 ms 40556 KB Output is correct
23 Correct 33 ms 41068 KB Output is correct
24 Correct 38 ms 41068 KB Output is correct
25 Correct 33 ms 41068 KB Output is correct
26 Correct 34 ms 41324 KB Output is correct
27 Correct 27 ms 40300 KB Output is correct
28 Correct 21 ms 40300 KB Output is correct
29 Correct 24 ms 40300 KB Output is correct
30 Correct 33 ms 40556 KB Output is correct
31 Correct 80 ms 41452 KB Output is correct
32 Correct 23 ms 40448 KB Output is correct
33 Correct 22 ms 40300 KB Output is correct
34 Correct 22 ms 40300 KB Output is correct
35 Correct 24 ms 40428 KB Output is correct
36 Correct 37 ms 40684 KB Output is correct
37 Correct 103 ms 41708 KB Output is correct
38 Correct 24 ms 40940 KB Output is correct
39 Correct 25 ms 40972 KB Output is correct
40 Correct 26 ms 40940 KB Output is correct
41 Correct 43 ms 41196 KB Output is correct
42 Correct 124 ms 42348 KB Output is correct
43 Correct 66 ms 52444 KB Output is correct
44 Correct 66 ms 52444 KB Output is correct
45 Correct 81 ms 52444 KB Output is correct
46 Correct 94 ms 52828 KB Output is correct
47 Correct 268 ms 54108 KB Output is correct
48 Correct 23 ms 40428 KB Output is correct
49 Correct 39 ms 40556 KB Output is correct
50 Correct 79 ms 41196 KB Output is correct
51 Correct 128 ms 41836 KB Output is correct
52 Correct 29 ms 41708 KB Output is correct
53 Correct 49 ms 41708 KB Output is correct
54 Correct 127 ms 42348 KB Output is correct
55 Correct 198 ms 43244 KB Output is correct
56 Correct 50 ms 46956 KB Output is correct
57 Correct 66 ms 47228 KB Output is correct
58 Correct 159 ms 47724 KB Output is correct
59 Correct 239 ms 48620 KB Output is correct
60 Correct 77 ms 53612 KB Output is correct
61 Correct 112 ms 53740 KB Output is correct
62 Correct 219 ms 54380 KB Output is correct
63 Correct 293 ms 55532 KB Output is correct
64 Correct 288 ms 55020 KB Output is correct
65 Correct 350 ms 57504 KB Output is correct
66 Correct 400 ms 57452 KB Output is correct
67 Correct 367 ms 57536 KB Output is correct
68 Correct 374 ms 57452 KB Output is correct
69 Correct 360 ms 57448 KB Output is correct
70 Correct 339 ms 57312 KB Output is correct
71 Correct 451 ms 60012 KB Output is correct
72 Correct 407 ms 60056 KB Output is correct
73 Correct 406 ms 59884 KB Output is correct
74 Correct 423 ms 60012 KB Output is correct
75 Correct 414 ms 59728 KB Output is correct
76 Correct 370 ms 59232 KB Output is correct
77 Correct 475 ms 63724 KB Output is correct
78 Correct 477 ms 63724 KB Output is correct
79 Correct 463 ms 63724 KB Output is correct
80 Correct 475 ms 63596 KB Output is correct
81 Correct 453 ms 62952 KB Output is correct
82 Correct 405 ms 60256 KB Output is correct
83 Correct 458 ms 63940 KB Output is correct
84 Correct 468 ms 63724 KB Output is correct
85 Correct 449 ms 63852 KB Output is correct
86 Correct 453 ms 63724 KB Output is correct
87 Correct 470 ms 63080 KB Output is correct
88 Correct 426 ms 60256 KB Output is correct
89 Correct 340 ms 56428 KB Output is correct
90 Correct 377 ms 56960 KB Output is correct
91 Correct 384 ms 58092 KB Output is correct
92 Correct 388 ms 58184 KB Output is correct
93 Correct 409 ms 60396 KB Output is correct
94 Correct 407 ms 59500 KB Output is correct
95 Correct 455 ms 61280 KB Output is correct
96 Correct 439 ms 60268 KB Output is correct
97 Correct 443 ms 60908 KB Output is correct
98 Correct 470 ms 62828 KB Output is correct
99 Correct 439 ms 60780 KB Output is correct
100 Correct 440 ms 60652 KB Output is correct