Submission #1308437

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308437		wangzhiyi33	Dynamic Diameter (CEOI19_diameter)	C++20	49 / 100	5102 ms	314068 KiB

diameter

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#define int long long 
#define fir first
#define sec second
#define pb push_back

const int maxn=1e5;
int n,qu,hihi;

vector<pair<int,int> >adj[maxn+2];
int dep[maxn+2],sub[maxn+2];
bool vis[maxn+2];

void ulang(int cur,int par){
    sub[cur]=1;
    for(auto x : adj[cur]){
        if(x.fir==par)continue;
        if(vis[x.fir]){
            sub[x.fir]=0; continue;
        }
        ulang(x.fir,cur);
        sub[cur]+=sub[x.fir];
    }
}

int centro(int cur,int par,int sz){
    for(auto x : adj[cur]){
        if(x.fir==par || vis[x.fir])continue;
        if(sub[x.fir]>=sz/2)return centro(x.fir,cur,sz);
    }
    return cur;
}

map<int,array<int,3> >mp[maxn+2];
int cnt,dist[maxn+2];

void euler(int cur,int par,int tot,int asal,int root){
    cnt++; dist[cnt]=tot;
    mp[root][cur]={cnt,0,asal};

    for(auto x : adj[cur]){
        if(x.fir==par || vis[x.fir])continue;
        euler(x.fir,cur,tot+x.sec,asal,root);
    }
    mp[root][cur][1]=cnt;
}

struct seg{
    int mx,lz,l,r;

    seg *lf,*rg;
    void build(int x,int y){
        l=x,r=y; lz=0;
        if(l==r){
            mx=dist[x];
            return;
        }

        int mid=(l+r)/2;
        lf=new seg(),rg=new seg();
        lf->build(l,mid),rg->build(mid+1,r);
        mx=max(lf->mx,rg->mx);
    }

    void apply(int brp){
        lz+=brp; mx+=brp;
    }

    void prop(){
        if(l==r || lz==0)return;
        lf->apply(lz),rg->apply(lz);
        lz=0;
    }

    void update(int posl,int posr,int brp){
        if(l>posr || r<posl)return ;
        if(l>=posl && r<=posr){
            apply(brp);
            return;
        }
        prop();
        lf->update(posl,posr,brp),rg->update(posl,posr,brp);
        mx=max(lf->mx,rg->mx);
    }

    int query(int posl,int posr){
        if(l>posr || r<posl)return 0;
        if(l>=posl && r<=posr)return mx;
        prop();
        return max(lf->query(posl,posr),rg->query(posl,posr));
    }

    int semua(){
        return mx;
    }
};

vector<seg*>isi[maxn+2];
multiset<int>cari[maxn+2];
int anc[maxn+2];

void solve(int cur,int prv){
    ulang(cur,-1);
    int root=centro(cur,prv,sub[cur]);

    vis[root]=true;
    dep[root]=dep[prv]+1;
    anc[root]=prv;
    int brp=-1;
    
    for(auto x : adj[root]){
        if(vis[x.fir])continue;
        cnt=0; brp++;
        euler(x.fir,root,x.sec,brp,root);

        // buat lazy segtree
        seg* apa=new seg(); apa->build(1,cnt);
        isi[root].pb(apa);
        cari[root].insert(apa->query(1,cnt));
    }
    
    for(auto x : mp[root]){
        // cout<<root<<" k "<<x.fir<<" "<<dist[x.fir]<<endl;
        dist[x.fir]=0;
    }

    for(auto x : adj[root]){
        if(vis[x.fir])continue;
        solve(x.fir,root);
    }

}
multiset<int>ans;

int mul(int idx){
    if(cari[idx].size()==0)return 0;

    auto it=cari[idx].end(); it--;
    int brp=*it;
    if(cari[idx].size()>=2){
        it--;
        brp+=*it;
    }
    return brp;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>qu>>hihi;   
    array<int,3> edge[n+1]; 
    for(int q=1;q<n;q++){
        int u,v,w;
        cin>>u>>v>>w;
        edge[q]={u,v,w};
        adj[u].pb({v,w});
        adj[v].pb({u,w});
    }

    solve(1,0);
    for(int q=1;q<=n;q++){
        ans.insert(mul(q));
    }

    int lastt=0;
    while(qu--){
        int d,e;
        cin>>d>>e;
        d=(d+lastt)%(n-1); d++;
        e=(e+lastt)%(hihi);

        auto [u,v,we]=edge[d];
        if(dep[u]>dep[v])swap(u,v);
        int slsh=e-we;
        

        int cur=u;
        while(cur!=0){
            array<int,3>uu=mp[cur][u];
            array<int,3>vv=mp[cur][v];
            if(uu[0]<vv[0])swap(uu,vv);

            ans.erase(ans.find(mul(cur)));
            
            cari[cur].erase(cari[cur].find(isi[cur][uu[2]]->semua()));
           // cout<<isi[cur][uu[2]]->semua()<<endl;

            isi[cur][uu[2]]->update(uu[0],uu[1],slsh);
            cari[cur].insert(isi[cur][uu[2]]->semua());
            ans.insert(mul(cur));

            cur=anc[cur];
        }

        edge[d][2]=e;
        cout<<*ans.rbegin()<<'\n';
        lastt=*ans.rbegin();
    }
}

/*
1. buat centroid
2. setiap nodenya buat euler tour -> in,out,asal
3. cek dist juga
4. buat lazy seg tree di setiap node
5. multiset dari max lazy

6. update cek yang mana lebih tinggi depnya mulai dari yang pendek
7. naik terus ke par centro
8. update sesuai euler tour dan lz yang benar
9. ganti multiset

*/

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