oj.uz

Submission #654800

# Submission time Handle Problem Language Result Execution time Memory
654800 2022-11-01T16:28:06 Z someone Dynamic Diameter (CEOI19_diameter) C++14
31 / 100
 622 ms 80108 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
 
struct Node {
    int deb, fin, tag, val[3][3];
};
 
const int M = 1 << 18, N = 2*M, INF = 1e18 + 42;
 
Node node[N];
vector<int> adj[N];
int n, q, w, id = 0, h[M], l[M], r[M], a[M], b[M], c[M];
 
int coeff[3][3] = {{1, -1, 1}, {0, -2, -1}, {0, 0, 1}};
 
void eulertour(int i = 0, int pre = 0, int depth = 0) {
    l[i] = id;
    h[i] = depth;
    depth++, id++;
    
    for(int j : adj[i])
        if(j != pre) {
            eulertour(j, i, depth);
            id++;
        }
    
    r[i] = id;
}

inline void applyOp(int i, int add) {
    node[i].tag += add;
    if(node[i].fin - node[i].deb == 1) {
        for(int j = 0; j < 3; j++)
            node[i].val[j][j] += coeff[j][j] * add;
    } else if(node[i].fin - node[i].deb == 2) {
        for(int j = 0; j < 3; j++)
            for(int k = j; k < 3; k++)
                node[i].val[j][k] += coeff[j][k] * add;
        node[i].val[0][2] = -INF;
    } else {
        for(int j = 0; j < 3; j++)
            for(int k = j; k < 3; k++)
                node[i].val[j][k] += coeff[j][k] * add;
    }
}

void update(int i, int d, int f, int add) {
    if(node[i].fin <= d || f <= node[i].deb)
        return;
    if(d <= node[i].deb && node[i].fin <= f) {
        applyOp(i, add);
        return;
    }
    int lChild = i*2, rChild = i*2+1;
    applyOp(lChild, node[i].tag);
    applyOp(rChild, node[i].tag);
    node[i].tag = 0;
    
    update(lChild, d, f, add);
    update(rChild, d, f, add);
    
    for(int j = 0; j < 3; j++)
        for(int k = j; k < 3; k++)
            node[i].val[j][k] = max(node[lChild].val[j][k], node[rChild].val[j][k]);
    for(int j = 0; j < 3; j++)
        for(int k = j; k < 3; k++)
            for(int l = k+1; l < 3; l++)
                node[i].val[j][l] = max(node[i].val[j][l], node[lChild].val[j][k] + node[rChild].val[k+1][l]);
}
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    for(int i = 0; i < N; i++) {
        node[i].tag = 0;
        for(int j = 0; j < 3; j++)
            for(int k = j; k < 3; k++)
                node[i].val[j][k] = 0;
        if(i >= M/2)
            node[i].val[0][2] = -INF;
        if(i >= M) {
            node[i].val[0][1] = -INF;
            node[i].val[1][2] = -INF;
        }
    }
    for(int i = M; i < N; i++)
        node[i].fin = 1 + (node[i].deb = i - M);
    for(int i = M-1; i > 0; i--)
        node[i].deb = node[i*2].deb,
        node[i].fin = node[i*2+1].fin;
    
    cin >> n >> q >> w;
    for(int i = 0; i < n-1; i++) {
        cin >> a[i] >> b[i] >> c[i];
        a[i]--, b[i]--;
        adj[a[i]].push_back(b[i]);
        adj[b[i]].push_back(a[i]);
    }
    eulertour();
    for(int i = 0; i < n-1; i++) {
        if(h[a[i]] > h[b[i]])
            swap(a[i], b[i]);
        update(1, l[b[i]], r[b[i]], c[i]);
    }
    int last = 0;
    for(int i = 0; i < q; i++) {
        int d, e; cin >> d >> e;
        d = (d + last) % (n-1);
        e = (e + last) % w;
        update(1, l[b[d]], r[b[d]], e - c[d]);
        c[d] = e;
        last = node[1].val[0][2];
        cout << last << '\n';
    }
}

Subtask #1
0 / 11.0

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

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 61860 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 35 ms 61872 KB Output is correct
2 Correct 40 ms 61864 KB Output is correct
3 Correct 42 ms 61900 KB Output is correct
4 Correct 53 ms 62036 KB Output is correct
5 Correct 116 ms 63032 KB Output is correct
6 Correct 37 ms 61892 KB Output is correct
7 Correct 36 ms 61888 KB Output is correct
8 Correct 38 ms 61964 KB Output is correct
9 Correct 38 ms 61984 KB Output is correct
10 Correct 59 ms 62204 KB Output is correct
11 Correct 119 ms 63180 KB Output is correct
12 Correct 44 ms 62392 KB Output is correct
13 Correct 46 ms 62388 KB Output is correct
14 Correct 43 ms 62412 KB Output is correct
15 Correct 58 ms 62684 KB Output is correct
16 Correct 130 ms 63844 KB Output is correct
17 Correct 122 ms 71672 KB Output is correct
18 Correct 123 ms 71632 KB Output is correct
19 Correct 144 ms 71800 KB Output is correct
20 Correct 149 ms 71948 KB Output is correct
21 Correct 271 ms 73356 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 62028 KB Output is correct
2 Incorrect 59 ms 62080 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 75852 KB Output is correct
2 Correct 438 ms 75796 KB Output is correct
3 Correct 406 ms 75980 KB Output is correct
4 Correct 539 ms 75844 KB Output is correct
5 Correct 423 ms 76044 KB Output is correct
6 Correct 357 ms 76072 KB Output is correct
7 Correct 446 ms 77548 KB Output is correct
8 Correct 530 ms 77660 KB Output is correct
9 Correct 448 ms 77556 KB Output is correct
10 Correct 496 ms 77540 KB Output is correct
11 Correct 471 ms 77544 KB Output is correct
12 Correct 422 ms 77236 KB Output is correct
13 Correct 542 ms 79864 KB Output is correct
14 Correct 622 ms 79948 KB Output is correct
15 Correct 573 ms 80032 KB Output is correct
16 Correct 564 ms 79964 KB Output is correct
17 Correct 544 ms 79656 KB Output is correct
18 Correct 491 ms 78172 KB Output is correct
19 Correct 590 ms 80024 KB Output is correct
20 Correct 591 ms 79928 KB Output is correct
21 Correct 572 ms 80108 KB Output is correct
22 Correct 561 ms 80028 KB Output is correct
23 Correct 571 ms 79708 KB Output is correct
24 Correct 449 ms 78088 KB Output is correct

Subtask #6
0 / 27.0

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