Submission #1301925

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301925		tudor_costin	Dynamic Diameter (CEOI19_diameter)	C++20	7 / 100	458 ms	102892 KiB

diameter

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int Nmax=1e5+5;
class AINT
{
private:
    vector<int> aint;
    vector<int> lazy;
    int n;
public:
    AINT(int siz):lazy(4*siz+5,0), aint(4*siz+5,0)
    {
        n=siz;
    }
    void propagate(int nod)
    {
        if(lazy[nod]==0) return;
        aint[2*nod]+=lazy[nod];
        aint[2*nod+1]+=lazy[nod];
        lazy[2*nod]+=lazy[nod];
        lazy[2*nod+1]+=lazy[nod];
        lazy[nod]=0;
        return;
    }
    int getmax()
    {
        return aint[1];
    }
    void update(int nod,int l,int r,int st,int dr,int val)
    {
        if(st<=l && r<=dr)
        {
            aint[nod]+=val;
            lazy[nod]+=val;
            return;
        }
        int mid=(l+r)/2;
        propagate(nod);
        if(dr<=mid) update(2*nod,l,mid,st,dr,val);
        else if(mid<st) update(2*nod+1,mid+1,r,st,dr,val);
        else
        {
            update(2*nod,l,mid,st,mid,val);
            update(2*nod+1,mid+1,r,mid+1,dr,val);
        }
        aint[nod]=max(aint[2*nod],aint[2*nod+1]);
    }
    void upd(int l,int r,int val)
    {
        update(1,0,n-1,l,r,val);
    }
};
vector<AINT> aints[Nmax];
multiset<int> bigC[Nmax];
struct edge
{
    int u;
    int v;
    int cost;
};
struct information
{
    int tata;
    int l;
    int r;
};
edge edges[Nmax];
vector<pair<int,int>> g[Nmax];
bool taken[Nmax];
int siz[Nmax],fc[Nmax],frunze[Nmax];
unordered_map<int,information> interv[Nmax];
unordered_map<int,int> nextCentroid[Nmax];
unordered_map<int,int> pozinG[Nmax];
multiset<int> allvals;
void getsizes(int nod,int pr)
{
    siz[nod]=1;
    frunze[nod]=0;
    bool ok=0;
    for(auto [u,id]:g[nod])
    {
        if(!taken[u] && u!=pr)
        {
            getsizes(u,nod);
            frunze[nod]+=frunze[u];
            ok=1;
            siz[nod]+=siz[u];
        }
    }
    ///cout<<nod<<' '<<pr<<' '<<siz[nod]<<'\n';
    if(!ok) frunze[nod]++;
}
int getcentroid(int nod,int pr,int tot)
{
    for(auto [u,id]:g[nod])
    {
        if(taken[u] || u==pr) continue;
        if(2*siz[u]>tot)
        {
            return getcentroid(u,nod,tot);
        }
    }
    return nod;
}
void buildaint(int nod,int pr,AINT &cur,int cntfr,int cost,int tata,int centroid)
{
    int l=cntfr,r=cntfr+frunze[nod]-1;
    cur.upd(l,r,cost);
    for(auto [u,id]:g[nod])
    {
        if(taken[u] || u==pr) continue;
        buildaint(u,nod,cur,cntfr,edges[id].cost,tata,centroid);
        interv[id][centroid]= {tata,cntfr,cntfr+frunze[u]-1};
        cntfr+=frunze[u];
    }
    return;
}
int getsum(multiset<int>& s)
{
    if(s.size()>=2)
    {
        auto it=s.rbegin();
        int sum=(*it);
        it++;
        sum+=(*it);
        return sum;
    }
    else return (*s.rbegin());
}
int decompBuild(int nod)
{
    getsizes(nod,0);
    int centroid=getcentroid(nod,0,siz[nod]);
    ///cout<<centroid<<' '<<"CENTROID"<<'\n';
    int cnt=0;
    for(auto [u,id]:g[centroid])
    {
        ///cout<<centroid<<' '<<u<<' '<<id<<'\n';
        if(taken[u]) continue;
        pozinG[u][centroid]=cnt;
        cnt++;
        AINT cur(frunze[u]);
        ///cout<<centroid<<' '<<u<<' '<<id<<'\n';
        interv[id][centroid]= {u,0,frunze[u]-1};
        ///cout<<centroid<<' '<<u<<' '<<id<<'\n';
        buildaint(u,centroid,cur,0,edges[id].cost,u,centroid);
        ///cout<<centroid<<' '<<u<<' '<<id<<' '<<cur.getmax()<<'\n';
        bigC[centroid].insert(cur.getmax());
        aints[centroid].push_back(cur);
        ///cout<<centroid<<' '<<u<<' '<<id<<'\n';
    }
    if(!bigC[centroid].empty()) allvals.insert(getsum(bigC[centroid]));
    taken[centroid]=1;
    for(auto [u,id]:g[centroid])
    {
        if(taken[u]) continue;
        nextCentroid[u][centroid]=decompBuild(u);
    }
    return centroid;
}
void update(int centroid,int id,int prv,int val)
{
    ///cout<<centroid<<' '<<id<<' '<<prv<<' '<<val<<'\n';
    auto [tata,l,r]=interv[id][centroid];
    if(!bigC[centroid].empty())
    {
        int poz=pozinG[tata][centroid];
        int cur=aints[centroid][poz].getmax();
        int curval=getsum(bigC[centroid]);
        ///cout<<curval<<'\n';
        allvals.erase(allvals.find(curval));
        bigC[centroid].erase(bigC[centroid].find(cur));
        ///cout<<l<<' '<<r<<'\n';
        aints[centroid][poz].upd(l,r,-prv);
        aints[centroid][poz].upd(l,r,val);
        int nw=aints[centroid][poz].getmax();
        bigC[centroid].insert(nw);
        ///cout<<centroid<<' '<<getsum(bigC[centroid])<<' '<<"UPDATE CENTROID"<<'\n';
        allvals.insert(getsum(bigC[centroid]));
    }
    if(edges[id].u==centroid && edges[id].v==tata) return;
    if(edges[id].u==tata && edges[id].v==centroid) return;
    int nxt=nextCentroid[tata][centroid];
    if(nxt!=0) update(nxt,id,prv,val);
    return;
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n,q,w;
    cin>>n>>q>>w;
    for(int i=1; i<n; i++)
    {
        cin>>edges[i].u>>edges[i].v>>edges[i].cost;
        g[edges[i].u].push_back({edges[i].v,i});
        g[edges[i].v].push_back({edges[i].u,i});
    }
    int firstCentroid=decompBuild(1);
    int last=0;
    ///cout<<111<<'\n';
    while(q--)
    {
        int d,e;
        cin>>d>>e;
        d=(d+last)%(n-1);
        e=(e+last)%w;
        d++;
        ///cout<<d<<' '<<e<<'\n';
        update(firstCentroid,d,edges[d].cost,e);
        edges[d].cost=e;
        last=(*allvals.rbegin());
        cout<<last<<'\n';
    }
    return 0;
}

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