Submission #1242958

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242958		yassia	Dynamic Diameter (CEOI19_diameter)	C++20	49 / 100	5022 ms	407256 KiB

diameter

#ifndef local
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
#define fs first
#define sn second
using pii = pair<int, int>;
using pll = pair<ll,ll>;
using str = string;
using ld = long double;
using hash_map =gp_hash_table<int, int>;
using hash_set= gp_hash_table <int, null_type>;
auto sd = std::chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rnd(sd);
typedef tree<ll, null_type, less<>, rb_tree_tag,
        tree_order_statistics_node_update> ord_set;
const ll maxn = 2e5+8;
const ll inf = 2e18+7;
ll n;
vector<vector<int>> g;
vector<vector<pair<int,ll>>> g1;
int del[maxn];
vector<multiset<ll>> ansforcentr;
vector<vector<int>> cntr;
void push(ll v, vector<ll> &d, vector<ll> &ps) {
    if (ps[v]== 0) return;
    ps[v*2]+= ps[v]; ps[v*2+1]+=ps[v];
    d[v*2]+=ps[v]; d[v*2+1]+=ps[v];
    ps[v] =0;
}
void upd(ll v, ll l, ll r, ll sl, ll sr, ll x, vector<ll> &d, vector<ll> &ps){
    push(v, d, ps);
    if (sl <= l && r <= sr){
        ps[v]+=x;
        d[v]+=x;
        push(v, d, ps);
        return;
    }
    else if (sr <= l || r <= sl){
        return;
    }
    push(v, d, ps);
    upd(v*2 ,l, (l+r)/2, sl, sr,x, d, ps);
    upd(v*2+1, (l+r)/2, r, sl, sr, x, d, ps);
    d[v]=max(d[v*2],d[v*2+1]);
}
ll get_max(ll v, ll l, ll r, ll sl, ll sr, vector<ll>&d, vector<ll>&ps){
    push(v, d, ps);
    if (sl <= l && r <= sr){
        return d[v];
    }
    else if (sr <= l || r <= sl) {
        return 0;
    }
    return max(get_max(v*2, l, (l+r)/2, sl, sr, d, ps), get_max(v*2+1, (l+r)/2, r, sl, sr, d, ps));
}
struct segtree{
    vector<ll> d;
    vector<ll> ps;
};

void df1(int v, vector<int> &comp, int p){
    comp.emplace_back(v);
    for (auto u : g[v]){
        if (!del[u] && u != p){
            df1(u,comp, v);
        }
    }
}
void cntp(int v, int &timer, vector<int>&pr,
          vector<int>&dp, vector<int>&tin, vector<int>&tout,
          unordered_map<int,int>&nm, vector<int>&ch,
          int p){
    pr[nm[v]] = nm[p];
    if (pr[nm[v]]==0) {
        ch[nm[v]] = nm[v];
    }
    else if (pr[pr[nm[v]]]==0){
        ch[nm[v]] = nm[v];
    }
    else ch[nm[v]] = ch[pr[nm[v]]];
    if (p != -1){
        dp[nm[v]] = dp[nm[p]]+1;
    }
    tin[nm[v]]= timer++;
    for (auto u: g[v]) {
        if (!del[u] && u != p){
            cntp(u, timer, pr, dp, tin, tout,  nm, ch, v);
        }
    }
    tout[nm[v]]= timer;
}
void dfs(int v, unordered_map<int,int>&nm,vector<int>&pr, vector<ll>&dist, vector<ll>&wei, int p){
    if (pr[nm[v]]!=0)dist[nm[v]] = dist[pr[nm[v]]] +wei[nm[v]];
    else dist[nm[v]] = 0;
    for (auto u : g[v]){
        if (!del[u] && u != p){
            dfs(u, nm, pr, dist, wei, v);
        }
    }
}
void assign_all(int N, vector<int> &tin,
vector<int> &tout,
vector<int> &pr,
vector<ll> &dist,
vector<ll>& wei,
vector<int>& dp,
vector<int>&ch){
    tin.assign(N+1, 0);
    tout.assign(N+1, 0);
    pr.assign(N+1, 0);
    dist.assign(N+1, 0);
    wei.assign(N+1, 0);
    dp.assign(N+1, 0);
    ch.assign(N+1, 0);
}
struct centroid_decomposition{
    int centr = 1;
    vector<int> comp_of_the_centroid;
    vector<int> tin;
    vector<int> tout;
    vector<int> pr;
    vector<ll> dist;
    vector<ll> wei;
    vector<int> dp;
    vector<int> ch;
    int timer= 0;
    unordered_map<int,int> num;
};
vector<centroid_decomposition> f;
vector<segtree> trees;
vector<vector<ll>>edges;
multiset<ll> all_answ;
void count_(centroid_decomposition &t){
    df1(t.centr ,t.comp_of_the_centroid, -1);
    ll N = t.comp_of_the_centroid.size();
    if (N == 1) {
        return;
    }
    assign_all(N,t.tin,t.tout,t.pr,t.dist,t.wei,t.dp, t.ch);
    for (int i = 0; i < t.comp_of_the_centroid.size(); i++){
        t.num[t.comp_of_the_centroid[i]] = i+1;
        cntr[t.comp_of_the_centroid[i]].emplace_back(t.centr);
    }
    cntp(t.centr, t.timer, t.pr, t.dp, t.tin, t.tout, t.num, t.ch,-1);
    for (int v:t.comp_of_the_centroid){
        for (auto [u, w1]:g1[v]){
            if (!del[u]){
                if (t.pr[t.num[u]]==t.num[v]){
                    t.wei[t.num[u]] = w1;
                }
                else t.wei[t.num[v]] = w1;
            }
        }
    }
    dfs(t.centr, t.num, t.pr, t.dist,t. wei, -1);

    trees[t.centr].ps.assign(8*t.timer, 0);
    trees[t.centr].d.assign(8*t.timer, 0);
    for (int i =1; i<= N;i++){
        upd(1, 0, t.timer, t.tin[i],t.tin[i]+1,t.dist[i], trees[t.centr].d, trees[t.centr].ps);
        upd(1, 0, t.timer, t.tout[i], t.tout[i], t.dist[i], trees[t.centr].d, trees[t.centr].ps);
    }
    for (auto u : g[t.centr]){
        if (!del[u]){
            ansforcentr[t.centr].insert(-get_max(1, 0, t.timer, t.tin[t.num[u]], t.tout[t.num[u]], trees[t.centr].d, trees[t.centr].ps));
        }
    }
    ll ans1 = -(* ansforcentr[t.centr].begin());
    ll ans0 = 0;
    if ( ansforcentr[t.centr].size()>1){
        ans0 = *( ansforcentr[t.centr].begin().operator++());
        ans0 = -ans0;
    }
    ansforcentr[t.centr] = ansforcentr[t.centr];
    all_answ.insert(-(ans0+ans1));
}


void sol_for_centr(int C, ll ej, int uu, int vv){
    int uu1 = f[C].num[uu];
    int vv1 = f[C].num[vv];
    if (f[C].pr[uu1]==vv1) {
        swap(uu1,vv1);
    }
    ll prev_wei = f[C].wei[vv1];
    f[C].wei[vv1] = ej;
    int changed = f[C].ch[vv1];
    ll prans1 = -(*ansforcentr[C].begin());
    ll prans0 = 0;
    if (ansforcentr[C].size()>1){
        auto h = *(ansforcentr[C].begin().operator++());
        prans0 = -h;
    }all_answ.erase(all_answ.find(-(prans1+prans0)));
    ansforcentr[C].erase(ansforcentr[C].find(-get_max(1, 0, f[C].timer, f[C].tin[changed], f[C].tout[changed], trees[C].d, trees[C].ps)));
    upd(1, 0, f[C].timer, f[C].tin[vv1], f[C].tout[vv1], f[C].wei[vv1]-prev_wei, trees[C].d, trees[C].ps);
    ansforcentr[C].insert(-get_max(1, 0, f[C].timer, f[C].tin[changed], f[C].tout[changed], trees[C].d, trees[C].ps));
    ll ans1 = -(*ansforcentr[C].begin());
    ll ans0 = 0;
    if (ansforcentr[C].size()>1){
        auto h = *(ansforcentr[C].begin().operator++());
        ans0 = -h;
    }
    all_answ.insert(-(ans1+ans0));
}
void change(ll dj, ll ej){
    int uu = edges[dj][0];
    int vv = edges[dj][1];
    unordered_map<int,int> cc;
    for (auto u : cntr[uu]){
        if (!f[u].tin.empty())
             cc[u]++;
    }
    for (auto v: cntr[vv]){
        if (!f[v].tin.empty()) cc[v]++;
    }
    vector<int> c1;
    for (auto x: cc) if (x.second>=2) c1.push_back(x.first);
    for (auto cur_centr: c1){
        sol_for_centr(cur_centr,  ej, uu, vv);
    }
}
ll S[maxn];
void fnd_sizes(int v,int p){
    S[v] =1;
    for (auto u : g[v]){
        if (u != p && !del[u]){
            fnd_sizes(u, v);
            S[v] += S[u];
        }
    }
}
int find_centr(int v, int p,ll sz){
    for (auto u : g[v]){
        if (u != p && !del[u] && S[u]>sz/2){
            return find_centr(u, v, sz);
        }
    }
    return v;
}
void centr_decomp(int v) {
    fnd_sizes(v, -1);
    f[v].centr = v;
    count_(f[v]);
    del[v] = 1;
    for (auto u : g[v]){
        if (!del[u]){
            centr_decomp(find_centr(u, v, S[u]));
        }
    }
}
void solve1() {
    ll  q, ww;
    cin >> n >> q>>ww;
    g.resize(n+1);
    g1.resize(n+1);
    for (int i =0; i < n-1; i++){
        int u, v;
        cin>>u>>v;   ll w; cin >> w;
        g[u].push_back(v);
        g[v].push_back(u);
        g1[u].emplace_back(v, w);
        g1[v].emplace_back(u,w);
        edges.push_back({u, v, w});
    }
    ll last = 0;
    f.resize(n+1);
    ansforcentr.resize(n+1);
    cntr.resize(n+1);
    trees.resize(n+1);
    centr_decomp(1);
    for (int i = 0; i <q; i++){
        ll dj, ej;
        cin>>dj>>ej;
        dj = (dj+last)%(n-1);
        ej = (ej+last)%ww;
        change(dj, ej);
        edges[dj][2] = ej;
        if (all_answ.empty()){
            cout<<0<<endl;
            last = 0;
        }
        else {
            last = -(*all_answ.begin());
            cout<< last<<endl;
        }
    }

}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef local
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif

    int t1 = 1;
    while (t1) solve1(), t1--;

#ifdef local
    printf_s("\n%.5f s", (double) clock() / CLOCKS_PER_SEC);
#endif
}

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