Submission #668350

#	Time	Username	Problem	Language	Result	Execution time	Memory
668350		someone	Dynamic Diameter (CEOI19_diameter)	C++14	100 / 100	637 ms	80088 KiB

diameter

#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, 0}, {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: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 27 / 27