oj.uz

Submission #654804

# Submission time Handle Problem Language Result Execution time Memory
654804 2022-11-01T16:50:40 Z someone Dynamic Diameter (CEOI19_diameter) C++14
31 / 100
 685 ms 76072 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(max(node[lChild].val[j][k], node[rChild].val[j][k]), -INF);
    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 35 ms 61892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 61892 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 38 ms 61920 KB Output is correct
2 Correct 37 ms 61848 KB Output is correct
3 Correct 40 ms 61884 KB Output is correct
4 Correct 56 ms 61900 KB Output is correct
5 Correct 125 ms 62356 KB Output is correct
6 Correct 36 ms 61896 KB Output is correct
7 Correct 41 ms 61880 KB Output is correct
8 Correct 36 ms 61844 KB Output is correct
9 Correct 39 ms 61872 KB Output is correct
10 Correct 56 ms 62024 KB Output is correct
11 Correct 131 ms 62392 KB Output is correct
12 Correct 43 ms 62292 KB Output is correct
13 Correct 41 ms 62336 KB Output is correct
14 Correct 46 ms 62360 KB Output is correct
15 Correct 62 ms 62412 KB Output is correct
16 Correct 145 ms 62808 KB Output is correct
17 Correct 134 ms 70532 KB Output is correct
18 Correct 183 ms 70464 KB Output is correct
19 Correct 130 ms 70464 KB Output is correct
20 Correct 163 ms 70576 KB Output is correct
21 Correct 310 ms 71072 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 61908 KB Output is correct
2 Incorrect 49 ms 62028 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 457 ms 71720 KB Output is correct
2 Correct 423 ms 71744 KB Output is correct
3 Correct 418 ms 71808 KB Output is correct
4 Correct 421 ms 71900 KB Output is correct
5 Correct 404 ms 71756 KB Output is correct
6 Correct 363 ms 71876 KB Output is correct
7 Correct 466 ms 73384 KB Output is correct
8 Correct 487 ms 73500 KB Output is correct
9 Correct 477 ms 73384 KB Output is correct
10 Correct 475 ms 73420 KB Output is correct
11 Correct 484 ms 73300 KB Output is correct
12 Correct 432 ms 73000 KB Output is correct
13 Correct 641 ms 75836 KB Output is correct
14 Correct 596 ms 75952 KB Output is correct
15 Correct 585 ms 75904 KB Output is correct
16 Correct 580 ms 75980 KB Output is correct
17 Correct 550 ms 75504 KB Output is correct
18 Correct 481 ms 74052 KB Output is correct
19 Correct 588 ms 75852 KB Output is correct
20 Correct 685 ms 76072 KB Output is correct
21 Correct 647 ms 75888 KB Output is correct
22 Correct 584 ms 75928 KB Output is correct
23 Correct 615 ms 75600 KB Output is correct
24 Correct 486 ms 73924 KB Output is correct

Subtask #6
0 / 27.0

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