Submission #1048915

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048915		andrey27_sm	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	324 ms	46660 KiB

diameter

//#pragma GCC optimze("O3,unroll-loops")
//#pragma GCC target("avx,avx2,bmi,bmi2")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr ll mod = 1e9 + 7;
vector<pair<int,int>> G[100001];
int p[100001];
ll dist[100001];
int tin[100001],tout[100001],timer;
struct sgt{
    int n;
    vector<ll> t;
    vector<ll> mod;
    sgt() = default;
    sgt(int n):n(n){
        t.resize(4*n);
        mod.resize(4*n);
    }
    void push(int v){
        if(mod[v]){
            t[v << 1] += mod[v];
            t[v << 1 | 1] += mod[v];
            mod[v << 1] += mod[v];
            mod[v << 1 | 1] += mod[v];
            mod[v] = 0;
        }
    }
    void update(int v,int l,int r,int tl,int tr,ll val){
        if(r < tl or l > tr)
            return;
        if(tl <= l and r <= tr){
            t[v] += val;
            mod[v] += val;
            return;
        }
        push(v);
        int m = (l + r) >> 1;
        update(v << 1,l,m,tl,tr,val);
        update(v << 1 | 1,m + 1,r,tl,tr,val);
        t[v] = max(t[v << 1],t[v << 1 | 1]);
    }
    ll query(int v,int l,int r,int tl,int tr){
        if(r < tl or l > tr)
            return 0;
        if(tl <= l and r <= tr)
            return t[v];
        push(v);
        int m = (l + r) >> 1;
        return max(query(v << 1,l,m,tl,tr),query(v << 1 | 1,m + 1,r,tl,tr));
    }
} tree;
ll edge[100001];
vector<pair<int,int>> Gt[100001];
void dfs1(int u,int par = -1){
    tin[u] = ++timer;
    for(auto [v,w]:G[u]){
        if(v == par)
            continue;
        dist[v] = dist[u] + w;
        p[v] = u;
        edge[v] = w;
        dfs1(v,u);
        Gt[u].push_back({tin[v],v});
    }
    tout[u] = timer;
}
multiset<ll> children[100001];
map<int,ll> chi[100001];
map<ll,int> ans;
ll dfs2(int v,int par = -1) {
    for (auto [u, w]: G[v]) {
        if (u == par)
            continue;
        ll W = dfs2(u, v)+w;
        children[v].insert(W);
        chi[v][u] = W;
    }

    if (children[v].empty())
        return 0;
    return *children[v].rbegin();
}
int n,q;
void update(int u,int v,ll w){
    if(p[u] != v) swap(u,v);
    tree.update(1,1,n,tin[u],tout[u],w-edge[u]);
    edge[u] = w;
}
ll check(int u, int v){  // v was updated
    auto e2 = *prev(lower_bound(Gt[u].begin(),Gt[u].end(),make_pair(tin[v],1'000'000'001)));
    v = e2.second;
    ll new_dist = tree.query(1,1,n,tin[v],tout[v])-tree.query(1,1,n,tin[u],tin[u]);
    children[u].erase(children[u].find(chi[u][v]));
    chi[u][v] = new_dist;
    children[u].insert(new_dist);
    if(children[u].size() == 1)
        return *children[u].rbegin();
    else if(children[u].size() >= 2){
        auto it = children[u].rbegin();
        ll x = *it;
        it++;
        ll y = *it;
        return x+y;
    }
    else return 0;
}
pair<int,int> edges[100001];
inline void solve(){
    ll W,w;
    cin >> n >> q >> W;
    for(int i = 0;i+1 < n;++i){
        int u,v;
        cin >> u >> v >> w;
        u--,v--;
        G[u].emplace_back(v,w);
        G[v].emplace_back(u,w);
        edges[i] = {u,v};
    }
    p[0] = -1;
    dfs1(0);
    tree = sgt(n);
    for(int i = 0;i < n;i++)
        tree.update(1,1,n,tin[i],tin[i],dist[i]);
    dfs2(0);
    ll last = 0;
    while(q--){
        ll i;
        ll w;
        cin >> i >> w;
        i+=last;
        w+=last;
        i%=(n-1);
        w%=W;
        //cerr << i << ' ' << w << '\n';
        int u = edges[i].first;
        int v = edges[i].second;
        update(u,v,w);
        if(p[v] != u) swap(u,v);
        cout << (last = check(0,v)) << '\n';
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while(t--)
        solve();
}

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