제출 #1242919

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1242919		yassia	Dynamic Diameter (CEOI19_diameter)	C++20	31 / 100	1060 ms	135076 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 int ll 
#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 = 3e5+8;
const ll inf = 2e18+7;
ll NN = maxn;
const ll logn = 20;
ll n;
vector<vector<ll>> g;
vector<vector<pll>> g1;
ll del[maxn];
vector<multiset<ll>> ansforcentr;
vector<vector<ll>> 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;
    }
    auto l1 = get_max(v*2, l, (l+r)/2, sl, sr, d, ps);
    auto l2 =get_max(v*2+1, (l+r)/2, r, sl, sr, d, ps);
    return max(l1 ,l2);
}
struct segtree{
    vector<ll> d;
    vector<ll> ps;
};

void df1(ll v, vector<ll> &comp, ll p){
    comp.emplace_back(v);
    for (auto u : g[v]){
        if (!del[u] && u != p){
            df1(u,comp, v);
        }
    }
}
void cntp(ll v, ll &timer, vector<ll>&pr,
          vector<ll>&dp, vector<ll>&tin, vector<ll>&tout, vector<vector<ll>>&bup,
          map<ll,ll>&nm,
          ll p){
    pr[nm[v]] = nm[p];
    if (p != -1){
        dp[nm[v]] = dp[nm[p]]+1;
    }
    tin[nm[v]]=timer++;
    for (auto u: g[v]) {
        if (!del[u] && nm[u] != nm[p]){
            cntp(u, timer, pr, dp, tin, tout, bup, nm,v);
            bup[0][nm[u]] = nm[v];
        }
    }
    tout[nm[v]]=timer++;
}
void dfs(ll v, map<ll,ll>&nm,vector<ll>&pr, vector<ll>&dist, vector<ll>&wei){
    if (pr[nm[v]]!=-1)dist[nm[v]] = dist[pr[nm[v]]] +wei[nm[v]];
    else dist[nm[v]] = 0;
    for (auto u : g[v]){
        if (!del[u] && nm[u] != pr[nm[v]] ){
            dfs(u, nm, pr, dist, wei);
        }
    }
}
void assign_all(ll N, vector<ll> &tin,
vector<ll> &tout,
vector<ll> &pr,
vector<ll> &dist,
vector<ll>& wei,
vector<ll>& dp,
vector<vector<int>> &bup){
    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);
    for (auto &vc: bup) vc.assign(N+1, 0);
}
struct centroid_decomposition{
    ll centr = 1;
    vector<ll> comp_of_the_centroid;
    vector<ll> tin;
    vector<ll> tout;
    vector<ll> pr;
    vector<ll> dist;
    vector<ll> wei;
    vector<ll> dp;
    ll timer= 0 ;
    vector<vector<ll>> bup;
    map<ll,ll> num;
};
vector<centroid_decomposition> f;
vector<segtree> trees;
vector<vector<ll>>edges;
multiset<pll> all_answ;
void count_(centroid_decomposition &t){
    df1(t.centr ,t.comp_of_the_centroid, -1);
    ll N = t.comp_of_the_centroid.size();
    t.bup.resize(logn+2);
    if (N == 1) {
        multiset<ll> r;
        r.insert(0);
        ansforcentr[t.centr] = r;
        return;
    }
    assign_all(N,t.tin,t.tout,t.pr,t.dist,t.wei,t.dp, t.bup);
    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.bup, t.num, -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);
    for (int lg = 1; lg <= logn; lg++){
        for (int i =1; i <= N;i++){
            t.bup[lg][i] = t.bup[lg-1][t.bup[lg-1][i]];
        }
    }

    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]+1, t.dist[i], trees[t.centr].d, trees[t.centr].ps);
    }
    multiset<ll> all;
    for (auto u : g[t.centr]){
        if (!del[u]){
            all.insert(-get_max(1, 0, t.timer, t.tin[t.num[u]], t.tout[t.num[u]]+1, trees[t.centr].d, trees[t.centr].ps));
        }
    }
    ll ans1 = -(*all.begin());
    ll ans0 = 0;
    if (all.size()>1){
        auto h = *(all.begin().operator++());
        ans0 = -h;
    }
    ansforcentr[t.centr] = all;
    all_answ.insert({-(ans0+ans1),t.centr});
}


void sol_for_centr(ll C, ll ej, ll uu, ll vv){
    ll uu1 = f[C].num[uu];
    ll 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;
    ll changed = vv1;
    for (int up = logn; up >= 0; up--){
        if (f[C].dp[f[C].bup[up][changed]]>=1){
            changed = f[C].bup[up][changed];
        }
    }
    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), C}));
    ansforcentr[C].erase(ansforcentr[C].find(-get_max(1, 0, f[C].timer, f[C].tin[changed], f[C].tout[changed]+1, trees[C].d, trees[C].ps)));
    upd(1, 0, f[C].timer, f[C].tin[vv1], f[C].tout[vv1]+1, 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]+1, 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), C});
}
void change(ll dj, ll ej){
    ll uu = edges[dj][0];
    ll vv = edges[dj][1];
    map<ll,ll> 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<ll> 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(ll v, ll 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(ll v, ll 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(ll v) {
    fnd_sizes(v, -1);
    f[v].centr = v;
    count_(f[v]);
    del[v] = 1;
    return;
    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;
    NN = 4*n;
    g.resize(n+1);
    g1.resize(n+1);
    for (int i =0; i < n-1; i++){
        ll u, v;
        cin>>u>>v;   ll w; cin >> w;
        g[u].push_back(v);
        g[v].push_back(u);
        g1[u].push_back({v, w});
        g1[v].push_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()->first);
            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: 0 / 11
• Subtask 2: 0 / 13
• Subtask 3: 7 / 7
• Subtask 4: 0 / 18
• Subtask 5: 24 / 24
• Subtask 6: 0 / 27