Submission #1125079

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125079		Zero_OP	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	1833 ms	171144 KiB

diameter

#include <bits/stdc++.h>

using namespace std;

const int MAX = 1e5 + 5;

struct segment_tree{
    vector<long long> st, lazy;
    segment_tree() : st(), lazy() {}

    void init(int n){
        st.resize(n << 2);
        lazy.resize(n << 2);
    }

    void apply(int id, long long v){
        st[id] += v;
        lazy[id] += v;
    }

    void down(int id){
        if(lazy[id] != 0){
            apply(id << 1, lazy[id]);
            apply(id << 1 | 1, lazy[id]);
            lazy[id] = 0;
        }
    }

    void update(int id, int l, int r, int u, int v, long long delta){
        if(u <= l && r <= v) apply(id, delta);
        else{
            int mid = l + r >> 1;
            down(id);
            if(u <= mid) update(id << 1, l, mid, u, v, delta);
            if(mid < v) update(id << 1 | 1, mid + 1, r, u, v, delta);
            st[id] = max(st[id << 1], st[id << 1 | 1]);
        }
    }

    long long query(int id, int l, int r, int u, int v){
        if(v < l || u > r) return 0;
        if(u <= l && r <= v) return st[id];
        int mid = l + r >> 1;
        down(id);
        return max(query(id << 1, l, mid, u, v), query(id << 1 | 1, mid + 1, r, u, v));
    }

    void build(int id, int l, int r, vector<long long>& val){
        if(l == r) st[id] = val[l];
        else{
            int mid = l + r >> 1;
            build(id << 1, l, mid, val);
            build(id << 1 | 1, mid + 1, r, val);
            st[id] = max(st[id << 1], st[id << 1 | 1]);
        }
    }
};

struct segment_2_best{
    vector<pair<long long, long long>> st;
    int n;
    segment_2_best() : st(n), n() {}

    void init(int _n){
        n = _n;
        st.resize(n * 2 + 10);
    }

    void update(int i, long long v){
        i += n;
        st[i] = {v, 0};
        for(; i > 1; i >>= 1){
            int p = i >> 1;
            st[p].first = max(st[i].first, st[i ^ 1].first);
            if(st[p].first == st[i].first) st[p].second = max(st[i].second, st[i ^ 1].first);
            else st[p].second = max(st[i].first, st[i ^ 1].second);
        }
    }

    long long sum_two_best(){
        if(st.empty()) return 0;
        assert((int)st.size() > 1);
        return st[1].first + st[1].second;
    }
};

int N, Q;
long long W;
int a[MAX], b[MAX];
long long c[MAX];
vector<int> adj_id[MAX];
int sz[MAX];
bool deleted[MAX];
segment_tree trs[MAX];
segment_2_best combinations[MAX];

long long t[MAX << 1];
void change(int i, long long v){
    i += N;
    t[i] = v;
    for(; i > 1; i >>= 1){
        t[i >> 1] = max(t[i], t[i ^ 1]);
    }
}

long long query_diameter(){
    return t[1];
}

int centroid_at[17][MAX], sz_seg[MAX];
int tin[17][MAX], tout[17][MAX], depth[MAX], id_subtree[17][MAX];
int l_sub[MAX], r_sub[MAX], represents[MAX];
int timer_subtree, timer_dfs;
vector<long long> tour(MAX), tour_subtree(MAX);

int dfs_sz(int u, int p){
    sz[u] = 1;
    for(auto id : adj_id[u]) if(p != id){
        int v = a[id] ^ b[id] ^ u;
        if(!deleted[v]) sz[u] += dfs_sz(v, id);
    }
    return sz[u];
}

int find_centroid(int u, int p, int target){
    for(auto id : adj_id[u]) if(p != id){
        int v = a[id] ^ b[id] ^ u;
        if(!deleted[v] && sz[v] * 2 > target) return find_centroid(v, id, target);
    }
    return u;
}

void initial_dfs(int u, int p, int layer, long long sum_w, int centroid){
    tour[tin[layer][u] = ++timer_dfs] = sum_w;
    id_subtree[layer][u] = timer_subtree;
    centroid_at[layer][u] = centroid;
    tour_subtree[timer_subtree] = max(tour_subtree[timer_subtree], sum_w);
//    cout << u << ' ' << p << ' ' << layer << ' ' << sum_w << ' ' << centroid << '\n';

    for(auto id : adj_id[u]) if(p != id){
        int v = a[id] ^ b[id] ^ u;
        if(deleted[v]) continue;
        if(p == -1){
            represents[++timer_subtree] = v;
        }
        initial_dfs(v, id, layer, sum_w + c[id], centroid);
    }
    tout[layer][u] = timer_dfs;
}

void decompose(int u, int dep){
    int cur = dfs_sz(u, -1);
    u = find_centroid(u, -1, cur);

    depth[u] = dep;
    timer_dfs = 0;
    l_sub[u] = timer_subtree;
    initial_dfs(u, -1, dep, 0, u);
    sz_seg[u] = timer_dfs;
    r_sub[u] = timer_subtree;
    if(r_sub[u] - l_sub[u] > 0) combinations[u].init(r_sub[u] - l_sub[u]);
    trs[u].init(sz_seg[u]);
    trs[u].build(1, 1, sz_seg[u], tour);
    for(int i = l_sub[u] + 1; i <= r_sub[u]; ++i) {
        if(l_sub[u] == r_sub[u]) assert(false);
        combinations[u].update(i - l_sub[u], tour_subtree[i]);
    }
    if(r_sub[u] - l_sub[u] > 0) {
//        cout << u << ' ' << combinations[u].sum_two_best() << '\n';
        change(u, combinations[u].sum_two_best());
    }
    deleted[u] = true;

    for(auto id : adj_id[u]){
        int v = a[id] ^ b[id] ^ u;
        if(deleted[v]) continue;
        decompose(v, dep + 1);
    }
}

void update(int id_e, long long new_w){
    long long delta = new_w - c[id_e];
    c[id_e] = new_w;
    int u = a[id_e], v = b[id_e];
    int mindep = min(depth[u], depth[v]);
    for(int i = mindep; i >= 0; --i){
        if(centroid_at[i][u] != -1 && centroid_at[i][v] != -1 && centroid_at[i][u] == centroid_at[i][v]){
            int c = centroid_at[i][u];
            if(tin[i][u] > tin[i][v]) swap(u, v);
            int id = id_subtree[i][v], k = represents[id];

            trs[c].update(1, 1, sz_seg[c], tin[i][v], tout[i][v], delta);

            int pos = id - l_sub[c];
            combinations[c].update(pos, trs[c].query(1, 1, sz_seg[c], tin[i][k], tout[i][k]));
            change(c, combinations[c].sum_two_best());
//            cout << c << " : " << combinations[c].sum_two_best() << '\n';
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    cin >> N >> Q >> W;
    for(int i = 0; i + 1 < N; ++i){
        cin >> a[i] >> b[i] >> c[i];
        --a[i]; --b[i];
        adj_id[a[i]].emplace_back(i);
        adj_id[b[i]].emplace_back(i);
    }

    memset(centroid_at, -1, sizeof(centroid_at));
    decompose(0, 0);

    long long last = 0;
    while(Q--){
        int d;
        long long e;
        cin >> d >> e;

        d = ((long long)d + last) % (N - 1);
        e = (e + last) % W;

        update(d, e);
        last = query_diameter();
        cout << last << '\n';
    }

    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 27 / 27