Submission #934458

#	Time	Username	Problem	Language	Result	Execution time	Memory
934458		sysia	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	3657 ms	187940 KiB

diameter

//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define int long long
typedef pair<int, int> T;
const int oo = 1e18, oo2 = 1e9+7, K = 17;
const int mod = 998244353;

struct Tree{
    vector<int>tab, lazy;
    int size = 1;

    Tree(int n){
        while (size < n) size*=2;
        tab.assign(2*size, -oo);
        lazy.assign(2*size, 0);
    }
    //dodaj na przedziale max na przedziale

    void update(int x, int lx, int rx, int pos, int val){
        if (lx == rx) {
            tab[x] = val;
            return;
        }
        int m = (lx+rx)/2;
        push(x);
        if (pos <= m) update(2*x, lx, m, pos, val);
        else update(2*x+1, m+1, rx, pos, val);
        tab[x] = max(tab[2*x], tab[2*x+1]);
    }

    void update(int x, int lx, int rx, int l, int r, int val){
        if (lx > r || rx < l) return;
        if (lx >= l && rx <= r){
            tab[x] += val;
            lazy[x] += val;
            return;
        }
        int m = (lx+rx)/2;
        push(x);
        update(2*x, lx, m, l, r, val);
        update(2*x+1, m+1, rx, l, r, val);
        tab[x] = max(tab[2*x], tab[2*x+1]);
    }

    void push(int x){
        if (!lazy[x]) return;
        for (auto k: {2*x, 2*x+1}){
            tab[k] += lazy[x];
            lazy[k] += lazy[x];
        }
        lazy[x] = 0;
    }

    int query(int x, int lx, int rx, int l, int r){
        if (lx > r || rx < l) return -oo;
        if (lx >= l && rx <= r) return tab[x];
        int m = (lx+rx)/2;
        push(x);
        return max(query(2*x, lx, m, l, r), query(2*x+1, m+1, rx, l, r));
    }
};

void solve(){
    int n, q, w; cin >> n >> q >> w;
    vector<vector<T>>g(n+1);
    vector<int>cost(n);
    for (int i = 1; i<n; i++){
        int a, b; cin >> a >> b >> cost[i];
        g[a].emplace_back(b, i);
        g[b].emplace_back(a, i);
    }   
    vector<int>sz(n+1);
    vector<bool>vis(n+1); 
    function<int(int, int)>getsz = [&](int v, int pa){
        sz[v] = 1;
        for (auto [x, i]: g[v]){
            if (x == pa || vis[x]) continue;
            sz[v] += getsz(x, v);
        }
        return sz[v];
    };
    function<int(int, int, int)>get_centroid = [&](int v, int pa, int ms){
        for (auto [x, i]: g[v]){
            if (x == pa || vis[x]) continue;
            if (2*sz[x] > ms) return get_centroid(x, v, ms);
        }
        return v;
    };

    int all = 0;
    Tree t(n * K);
    vector<multiset<int>>vals(n+1);
    vector<int>depth(n+1), ord;
    vector<vector<array<int, 6>>>where(n+1);
    multiset<int>ans;
    auto get = [&](int c){
        if ((int)vals[c].empty()) return -oo;
        if ((int)vals[c].size() == 1) return *vals[c].rbegin();
        debug(c, vals[c]);
        auto it = --(vals[c].end());
        int ans = *it;
        it--;
        ans += *it;
        debug(ans);
        return ans;
    };
    function<void(int)>centroid = [&](int c){
        c = get_centroid(c, c, getsz(c, c));
        getsz(c, c);
        function<void(int, int, int, int)>dfs = [&](int v, int pa, int from, int pos){
            for (auto [x, i]: g[v]){
                if (x == pa || vis[x]) continue;
                from = (v == pa ? x : from);
                pos = (v == pa ? all : pos);
                // if (v == pa) SZ[{c, from}] = {sz[from], all};
                // pos[{c, i}] = {all++, from};
                // ord.emplace_back(sz[x]);
                where[i].emplace_back(array<int, 6>{c, all++, from, pos, sz[from], sz[x]});
                depth[x] = depth[v] + cost[i];
                t.update(1, 0, t.size-1, all-1, depth[x]);
                dfs(x, v, from, pos);
                if (v == pa){
                    vals[c].insert(t.query(1, 0, t.size-1, pos, pos+sz[x]-1));
                }
            }
        };
        depth[c] = 0;
        dfs(c, c, -1, -1);
        ans.insert(get(c));
        debug(c, vals[c]);
        vis[c] = 1;
        for (auto [x, i]: g[c]){
            if (!vis[x]){
                centroid(x);
            }
        }
    };
    centroid(1);
    int last = 0;
    debug(ord);
    while (q--){
        int i, waga; cin >> i >> waga;
        i = (i+last)%(n-1) + 1;
        waga = (waga+last)%w;
        debug(i, cost[i], waga);
        int diff = waga - cost[i];
        cost[i] = waga;
        for (auto [c, pos, from, lfrom, szfr, szx]: where[i]){
            debug(c, all, from);
            ans.erase(ans.find(get(c)));
            vals[c].erase(vals[c].find(t.query(1, 0, t.size-1, lfrom, lfrom+szfr-1)));
            t.update(1, 0, t.size-1, pos, pos+szx-1, diff);
            vals[c].insert(t.query(1, 0, t.size-1, lfrom, lfrom+szfr-1));
            ans.insert(get(c));
        } 
        last = *ans.rbegin();
        cout << last << "\n";
        // return;
    }
}

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

    solve();

    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