Submission #1262467

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262467		LeonidCuk	Dynamic Diameter (CEOI19_diameter)	C++20	0 / 100	261 ms	20904 KiB

diameter

#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<int,long long>>>g;
vector<long long>es,en,st,kojedge,lazy(4e5+10);
int timer=0;
void push_lazy(int i,int l,int r)
{
    if(lazy[i]==0)return;
    st[i]+=lazy[i];
    if(l!=r)
    {
        lazy[2*i]+=lazy[i];
        lazy[2*i+1]+=lazy[i];
    }
    lazy[i]=0;
}
void update(int i,int l,int r,int tl,int tr,long long x)
{
    push_lazy(i,l,r);
    if(l>r||tl>r||l>tr)return;
    if(tl<=l&&r<=tr)
    {
        lazy[i]=x;
        push_lazy(i,l,r);
        return;
    }
    int m=(l+r)/2;
    update(2*i,l,m,tl,tr,x);
    update(2*i+1,m+1,r,tl,tr,x);
    st[i]=max(st[2*i],st[2*i+1]);
}
long long getmax(int i,int l,int r,int tl,int tr)
{
    push_lazy(i,l,r);
    if(l>r||tl>r||l>tr)return 0;
    if(tl<=l&&r<=tr)return st[i];
    int m=(l+r)/2;
    return max(getmax(2*i,l,m,tl,tr),getmax(2*i+1,m+1,r,tl,tr));
}
void dfs(int a,int b)
{
    es[a]=timer;timer++;
    for(auto i:g[a])
    {
        if(i.first!=b)dfs(i.first,a);
    }
    en[a]=timer-1;
}
void dfs1(int a,int b,int k)
{
    kojedge[a]=k;
    for(auto i:g[a])
    {
        if(i.first!=b)dfs1(i.first,a,k);
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    long long n,q,w,a,b,c,last=0;
    cin>>n>>q>>w;
    kojedge.resize(n+1);
    es.resize(n+1);
    st.resize(4*n+5);
    en.resize(n+1);
    g.resize(n+1);
    vector<pair<int,pair<int,long long>>>v;
    for(int i=0;i<n-1;i++)
    {
        cin>>a>>b>>c;
        v.push_back({a,{b,c}});
        g[a].push_back({b,c});
        g[b].push_back({a,c});
    }
    dfs(1,1);
    for(int i=0;i<n-1;i++)
    {
        int a=v[i].second.first;
        if(es[v[i].first]>es[a])a=v[i].first;
        update(1,0,n-1,es[a],en[a],v[i].second.second);
    }
    a=1;
    vector<int>usteden(n+1);
    set<pair<long long,int>>s;
    for(auto i:g[1])
    {
        dfs1(i.first,a,last);
        long long t=getmax(1,0,n-1,es[i.first],en[i.first]);
        s.insert({t,last});
        usteden[last]=t;
        last++;
    }
    last=0;
    for(int i=0;i<q;i++)
    {
        cin>>a>>b;
        a=(a+last)%(n-1);
        b=(b+last)%w;
        int a1=v[a].first,b1=v[a].second.first;
        if(es[a1]<es[b1])swap(a1,b1);
        b1=kojedge[a1];
        update(1,0,n-1,es[a1],en[a1],b-v[a].second.second);
        s.erase({usteden[b1],b1});
        a1=g[1][b1].first;
        usteden[b1]=getmax(1,0,n-1,es[a1],en[a1]);
        s.insert({usteden[b1],b1});
        last=0;
        auto it=s.rbegin();
        last+=it->first;
        it++;
        if(it!=s.rend())
        {
            last+=it->first;
        }
        cout<<last<<endl;
    }
}

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