Submission #934450

#	Time	Username	Problem	Language	Result	Execution time	Memory
934450		sysia	Dynamic Diameter (CEOI19_diameter)	C++17	31 / 100	5035 ms	257836 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), pre(n+1);
    vector<bool>vis(n+1); 
    int tt = 0;
    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;
    };
    vector<T>ord;
    vector<T>seg(n+1);
    int all = 0;
    map<T, T>pos;
    Tree t(n * K);
    vector<multiset<int>>vals(n+1);
    vector<int>depth(n+1);
    vector<vector<int>>where(n+1);
    multiset<int>ans;
    map<T, T>SZ;
    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);
        seg[c] = {all, all+sz[c]-2};
        function<void(int, int, int)>dfs = [&](int v, int pa, int from){
            for (auto [x, i]: g[v]){
                if (x == pa || vis[x]) continue;
                from = (v == pa ? x : from);
                if (v == pa) SZ[{c, from}] = {sz[from], all};
                pos[{c, i}] = {all++, from};
                ord.emplace_back(x, sz[x]);
                where[i].emplace_back(c);
                depth[x] = depth[v] + cost[i];
                t.update(1, 0, t.size-1, all-1, depth[x]);
                dfs(x, v, from);
            }
        };
        depth[c] = 0;
        dfs(c, c, -1);
        for (auto [x, i]: g[c]){
            if (vis[x]) continue;
            int l = pos[{c, i}].first;
            int ll = ord[l].second;
            if (ll >= 1) vals[c].insert(t.query(1, 0, t.size-1, l, l+ll-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(ans);
    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: where[i]){
            debug(c);
            auto [l, from] = pos[{c, i}];
            auto [v, s] = ord[l];
            debug(l, from, v, s);
            ans.erase(ans.find(get(c)));
            auto [s2, ls] = SZ[{c, from}];
            debug(from, ls, s2);
            if (s2 >= 1){
                int mx = t.query(1, 0, t.size-1, ls, ls+s2-1); //ale ja chce dla from
                debug(mx);
                vals[c].erase(vals[c].find(mx));
            }
            if (s >= 1) t.update(1, 0, t.size-1, l, l+s-1, diff);
            if (s2 >= 1){
                int mx = t.query(1, 0, t.size-1, ls, ls+s2-1); //ale ja chce dla from
                debug(mx);
                vals[c].insert(mx);
            }
            debug(vals[c], get(c));
            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);

    int t = 1;
    //cin >> t;
    while (t--) solve();

    return 0;
}

Compilation message (stderr)

diameter.cpp: In function 'void solve()':
diameter.cpp:98:9: warning: unused variable 'tt' [-Wunused-variable]
   98 |     int tt = 0;
      |         ^~

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