Submission #1165522

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165522		12345678	Dynamic Diameter (CEOI19_diameter)	C++20	100 / 100	4307 ms	222240 KiB

diameter

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e5+5, kx=17;

ll n, q, W, u[nx], v[nx], w[nx], pw[nx], sz[nx], used[nx], lvlc[nx], c[nx], t, in[nx][kx], out[nx][kx], hd[nx][kx], szc[nx], ssz, tmp[nx];
ll cres[nx], idx, vl;
vector<ll> d[nx];
multiset<ll> ms;

struct segtree
{
    vector<ll> lz[nx];
    vector<pair<ll, ll>> d[nx];
    void pushlz(int tidx, int l, int r, int i)
    {
        d[tidx][i].first+=lz[tidx][i];
        if (l!=r) lz[tidx][2*i]+=lz[tidx][i], lz[tidx][2*i+1]+=lz[tidx][i];
        lz[tidx][i]=0;
    }
    void build(int tidx, int l, int r, int i)
    {
        lz[tidx][i]=0;
        if (l==r) return d[tidx][i]={0, tmp[l]}, void();
        int md=(l+r)/2;
        build(tidx, l, md, 2*i);
        build(tidx, md+1, r, 2*i+1);
        d[tidx][i]=max(d[tidx][2*i], d[tidx][2*i+1]);
    }
    void update(int tidx, int l, int r, int i, int ql, int qr, ll vl)
    {
        pushlz(tidx, l, r, i);
        if (qr<l||r<ql) return;
        if (ql<=l&&r<=qr) return lz[tidx][i]+=vl, pushlz(tidx, l, r, i), void();
        int md=(l+r)/2;
        update(tidx, l, md ,2*i, ql, qr, vl);
        update(tidx, md+1, r, 2*i+1, ql, qr, vl);
        d[tidx][i]=max(d[tidx][2*i], d[tidx][2*i+1]);
    }
    pair<ll, ll> query(int tidx, int l, int r, int i, int ql, int qr)
    {
        pushlz(tidx, l, r, i);
        if (qr<l||r<ql||qr<ql) return {0, 0};
        if (ql<=l&&r<=qr) return d[tidx][i];
        int md=(l+r)/2;
        return max(query(tidx, l, md, 2*i, ql, qr), query(tidx, md+1, r, 2*i+1, ql, qr));
    }
} s;

int dfssz(int u, int p)
{
    sz[u]=1;
    for (auto v:d[u]) if (v!=p&&!used[v]) sz[u]+=dfssz(v, u);
    return sz[u];
}

int findcentroid(int u, int p, int rtsz)
{
    for (auto v:d[u]) if (v!=p&&!used[v]&&2*sz[v]>rtsz) return findcentroid(v, u, rtsz);
    return u;
}

void fillval(int u, int p, int h, int curlvl)
{
    in[u][curlvl]=++t;
    tmp[t]=h;
    hd[u][curlvl]=h;
    for (auto v:d[u]) if (v!=p&&!used[v]) fillval(v, u, h, curlvl);
    out[u][curlvl]=t;
}

void decomposition(int u, int p)
{
    ssz=dfssz(u, u);
    u=findcentroid(u, u, ssz);
    if (p!=-1) lvlc[u]=lvlc[p]+1;
    else lvlc[u]=0;
    c[u]=p;
    used[u]=1;
    t=1;
    for (auto v:d[u]) if (!used[v]) fillval(v, u, v, lvlc[u]);
    szc[u]=ssz;
    ms.insert(0);
    //cout<<"here "<<u<<'\n';
    s.d[u].resize(4*szc[u]);
    s.lz[u].resize(4*szc[u]);
    s.build(u, 1, ssz, 1);
    for (auto v:d[u]) if (!used[v]) decomposition(v, u);
}

void update(int idx, ll vl)
{
    ll delta=vl-pw[idx];
    pw[idx]=vl;
    if (lvlc[u[idx]]>lvlc[v[idx]]) swap(u[idx], v[idx]);
    int cur=u[idx];
    while (cur!=-1)
    {
        //cout<<"update "<<cur<<'\n';
        ms.erase(ms.find(cres[cur]));
        if (in[v[idx]][lvlc[cur]]<=in[u[idx]][lvlc[cur]]&&out[u[idx]][lvlc[cur]]<=out[v[idx]][lvlc[cur]]) swap(u[idx], v[idx]);
        //cout<<"here v "<<u[idx]<<' '<<v[idx]<<'\n';
        s.update(cur, 1, szc[cur], 1, in[v[idx]][lvlc[cur]], out[v[idx]][lvlc[cur]], delta);
        pair<ll, ll> mx=s.query(cur, 1, szc[cur], 1, 1, szc[cur]);
        mx.first+=max(s.query(cur, 1, szc[cur], 1, 1, in[mx.second][lvlc[cur]]-1), s.query(cur, 1, szc[cur], 1, out[mx.second][lvlc[cur]]+1, szc[cur])).first;
        cres[cur]=mx.first;
        ms.insert(cres[cur]);
        cur=c[cur];
    }
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>q>>W;
    for (int i=0; i<n-1; i++) cin>>u[i]>>v[i]>>w[i], d[u[i]].push_back(v[i]), d[v[i]].push_back(u[i]);
    decomposition(1, -1);
    //for (int i=1; i<=n; i++) cout<<i<<' '<<szc[i]<<' '<<lvlc[i]<<' '<<c[i]<<'\n';
    for (int i=0; i<n-1; i++) update(i, w[i]);
    //cout<<"finish\n";
    ll lst=0;
    while (q--)
    {
        cin>>idx>>vl;
        idx=(idx+lst)%(n-1);
        vl=(vl+lst)%W;
        update(idx, vl);
        lst=*prev(ms.end());
        cout<<lst<<'\n';
    }
}

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