oj.uz

Submission #651821

# Submission time Handle Problem Language Result Execution time Memory
651821 2022-10-20T07:55:06 Z someone Dynamic Diameter (CEOI19_diameter) C++14
31 / 100
 674 ms 79992 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;
    for(int j = 0; j < 3; j++)
        for(int k = 0; 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 = 0; 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 < 9; j++)
            node[i].val[j % 3][j / 3] = 0;
    }
    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 34 ms 61904 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 61904 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 61816 KB Output is correct
2 Correct 34 ms 61872 KB Output is correct
3 Correct 35 ms 62012 KB Output is correct
4 Correct 54 ms 62156 KB Output is correct
5 Correct 138 ms 62976 KB Output is correct
6 Correct 36 ms 61788 KB Output is correct
7 Correct 34 ms 61892 KB Output is correct
8 Correct 34 ms 61848 KB Output is correct
9 Correct 36 ms 61904 KB Output is correct
10 Correct 61 ms 62208 KB Output is correct
11 Correct 130 ms 63172 KB Output is correct
12 Correct 39 ms 62388 KB Output is correct
13 Correct 39 ms 62412 KB Output is correct
14 Correct 43 ms 62440 KB Output is correct
15 Correct 78 ms 62612 KB Output is correct
16 Correct 145 ms 63768 KB Output is correct
17 Correct 147 ms 71648 KB Output is correct
18 Correct 143 ms 71620 KB Output is correct
19 Correct 137 ms 71764 KB Output is correct
20 Correct 168 ms 72052 KB Output is correct
21 Correct 315 ms 73380 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 61932 KB Output is correct
2 Incorrect 57 ms 62112 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 486 ms 75856 KB Output is correct
2 Correct 519 ms 75800 KB Output is correct
3 Correct 468 ms 75812 KB Output is correct
4 Correct 463 ms 75848 KB Output is correct
5 Correct 472 ms 75884 KB Output is correct
6 Correct 428 ms 76116 KB Output is correct
7 Correct 529 ms 77484 KB Output is correct
8 Correct 525 ms 77576 KB Output is correct
9 Correct 509 ms 77584 KB Output is correct
10 Correct 546 ms 77484 KB Output is correct
11 Correct 533 ms 77464 KB Output is correct
12 Correct 479 ms 77236 KB Output is correct
13 Correct 674 ms 79948 KB Output is correct
14 Correct 636 ms 79944 KB Output is correct
15 Correct 647 ms 79948 KB Output is correct
16 Correct 649 ms 79980 KB Output is correct
17 Correct 666 ms 79676 KB Output is correct
18 Correct 521 ms 78144 KB Output is correct
19 Correct 653 ms 79936 KB Output is correct
20 Correct 617 ms 79888 KB Output is correct
21 Correct 591 ms 79992 KB Output is correct
22 Correct 658 ms 79924 KB Output is correct
23 Correct 668 ms 79792 KB Output is correct
24 Correct 583 ms 78132 KB Output is correct

Subtask #6
0 / 27.0

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