Submission #1105952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105952		kbtdauma	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	3409 ms	136244 KiB

diameter

#include <bits/stdc++.h>                /// D__P
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const ll mod = 1e9+7;
const int hh = 1e5+5;
const int hd = 1e5+5;
#define little signed main()
#define happy ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define I_love_Hoang_Diep(filename) freopen(filename".inp","r",stdin); freopen(filename".out","w",stdout);
#define TIME (1.0*clock()/CLOCKS_PER_SEC)
#define for0(i,n) for(int i=0;i<n;i++)
#define foru(i,a,b) for(int i=a;i<=b;i++)
#define ford(i,a,b) for(int i=a;i>=b;i--)
#define all(s) (s).begin(),(s).end()
#define sz(a) (a).size()
#define ms(f,v) memset((f),v,sizeof(f))
#define gcd __gcd
#define lcm(a,b) (a*b)/gcd(a,b)
#define vll vector<ll>
#define vi vector<int>
#define pf push_front
#define pb push_back
#define pll pair<ll,ll>
#define pii pair<int,int>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define mp make_pair
#define fi first
#define se second
#define bit(i,j) ((i>>j)&1)
#define log2(x) (63-__builtin_clzll(x))
using namespace std;
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
ll Rand(ll l,ll r)
{
    return l+(rd()*1LL*rd()%(r-l+1)+(r-l+1))%(r-l+1);
}

int n,Q;
ll W;
struct Edge
{
    int x,y;
    ll z;
    Edge(int _x=0,int _y=0,ll _z=0)
    {
        x=_x; y=_y; z=_z;
    }
} edge[hh];
vector<int> a[hh];
void nhap()
{
    cin>>n>>Q>>W;
    int x,y; ll z;
    foru(i,2,n)
    {
        cin>>x>>y>>z;
        a[x].pb(y);
        a[y].pb(x);
        edge[i-1]=Edge(x,y,z);
    }
}

struct SegTree
{
    ll t[4*hh], q[4*hh];
    void lp(int p,int l,int r)
    {
        if(!q[p]) return;
        t[p]+=q[p];
        if(l!=r) q[p<<1]+=q[p], q[p<<1|1]+=q[p];
        q[p]=0;
    }

    void update(int p,int l,int r,int u,int v,ll val)
    {
        lp(p,l,r);
        if(u>r||l>v) return;
        if(u<=l&&r<=v)
        {
            q[p]+=val;
            lp(p,l,r);
            return;
        }
        int m=l+r>>1;
        update(p<<1,l,m,u,v,val); update(p<<1|1,m+1,r,u,v,val);
        t[p]=max(t[p<<1],t[p<<1|1]);
    }

    void update(int l,int r,ll val)
    {
        update(1,1,n,l,r,val);
    }

    ll get(int p,int l,int r,int u,int v)
    {
        lp(p,l,r);
        if(u>r||l>v) return 0;
        if(u<=l&&r<=v) return t[p];
        int m=l+r>>1;
        return max(get(p<<1,l,m,u,v),get(p<<1|1,m+1,r,u,v));
    }

    ll get(int l,int r)
    {
        return get(1,1,n,l,r);
    }
}; 

struct CentroidDecomposition
{
    int sz[hh],par[hh], id, depth[hh];
    int in[log2(hh)+2][hh],out[log2(hh)+2][hh];
    void dfs(int u,int p)
    {
        sz[u]=1; id++;
        for(int x:a[u])
        {
            if(x==p||par[x]) continue;
            dfs(x,u);
            sz[u]+=sz[x];
        }
    }

    int FindCentroid(int u,int p)
    {
        for(int x:a[u])
            if(x!=p&&!par[x]&&sz[x]>(id>>1)) return FindCentroid(x,u);
        return u;
    }

    vector<int> edge[hh];
    int root, ans, layer, layer_id[hh], rt[log2(hh)+2][hh], ti[hh], Spar[log2(hh)+2][hh];
    void EulerTour(int u,int p)
    {
       // cout<<u<<' '<<p<<' '<<ans<<'\n';
        rt[layer][u]=ans;
        in[layer][u]=++ti[layer];
        if(p==ans) Spar[layer][u]=u;
        else Spar[layer][u]=Spar[layer][p];
        for(int x:a[u])
            if(x!=p&&!par[x]) EulerTour(x,u);
        out[layer][u]=ti[layer];
    }

    void BuildCentroidTree(int u,int p)
    {
        id=0; dfs(u,0);
        ans=FindCentroid(u,0);
        EulerTour(ans,0); layer_id[ans]=layer;
        if(!p) par[ans]=root=ans;
        else
        {
            par[ans]=p;
            depth[ans]=depth[p]+1;
        }
        for(int x:a[ans])
            if(!par[x]) edge[ans].pb(x);//, cout<<ans<<' '<<x.se<<'\n'; cout<<"\n";
        for(int x:a[ans])
        {
            if(!par[x]) 
            {
                layer++;
                BuildCentroidTree(x,ans);
                layer--;
            }
        }
    }
} CT; 

struct SegTreeIterative
{
	ll T[hh<<1];
	void update(int pos,ll val)
    {
		for(pos+=hh,T[pos]=val,pos>>=1;pos>0;pos>>=1) 
            T[pos]=max(T[pos<<1],T[pos<<1|1]);
	}
 
	ll get(ll l,ll r)
    {
		ll ans = 0;
		for(l+=hh,r+=hh+1;l<r;l>>=1,r>>=1)
        {
			if(l&1) ans=max(T[l++],ans);
			if(r&1) ans=max(ans,T[--r]);
		}
		return ans;
	}
} ST;

namespace d__p
{
    SegTree T[log2(hh)+2];
    map<ll,int> S[hh];
    ll ans=0;

    void Erase(int root,ll val)
    {
        S[root][val]--;
        if(!S[root][val]) S[root].erase(val);
    }

    void solve()
    {
        ll d,e; 
        int u,v,w,id;
        while(Q--)
        {
            cin>>d>>e;
            d=1+(d+ans)%(n-1);
            e=(e+ans)%W;
            u=edge[d].x, v=edge[d].y;
            ans=0;
            for0(j,log2(n))
            {
                if(CT.rt[j][u]!=CT.rt[j][v]) break;
                if(CT.in[j][u]<CT.in[j][v]) swap(u,v);
                int w=CT.Spar[j][u], root=CT.rt[j][v];
                //cout<<root<<' '<<w<<'\n';
                //S[root].erase(S[root].find(T[j].get(CT.in[j][w],CT.out[j][w])));
                Erase(root,T[j].get(CT.in[j][w],CT.out[j][w]));
                T[j].update(CT.in[j][u],CT.out[j][u],e-edge[d].z);
                S[root][T[j].get(CT.in[j][w],CT.out[j][w])]++;
                ll res=0; int idd=2;
                auto it=S[root].end();
                for0(j,2)
                {
                    if(idd<0) break;
                    if(it!=S[root].begin())
                    {
                        it=prev(it);
                        res+=(*it).fi*min((*it).se,idd);
                        idd-=(*it).se;
                    }
                }
                ST.update(root,res);
                //cout<<'\n';
                //cout<<u<<' '<<v<<' '<<root<<' '<<ans1<<' '<<e<<'\n';
            }
            edge[d].z=e;
            ans=ST.get(1,n);
            cout<<ans<<'\n';
        }
    }

    void hoangdiep()
    {
        //LCA.build();
        CT.BuildCentroidTree(1,0);
        foru(i,1,n-1)
        {
            int x=edge[i].x, y=edge[i].y;
            ll z=edge[i].z;
            for0(j,log2(n))
            {
                if(CT.rt[j][x]!=CT.rt[j][y]) break;
                if(CT.in[j][x]<CT.in[j][y]) swap(x,y);
                T[j].update(CT.in[j][x],CT.out[j][x],z);
            }
        }
        foru(i,1,n)
        {
            int id=CT.layer_id[i];
            for(int x:CT.edge[i])
                S[i][T[id].get(CT.in[id][x],CT.out[id][x])]++;//, cout<<i<<' '<<x.se<<'\n';
            ll res=0; int idd=2;
            auto it=S[i].end();
            for0(j,2)
            {
                if(idd<0) break;
                if(it!=S[i].begin())
                {
                    it=prev(it);
                    res+=(*it).fi*min((*it).se,idd);
                    idd-=(*it).se;
                }
            }
            ST.update(i,res);
        }
        solve();
       // cout<<1;
    }
}
little
{
    happy; //I_love_Hoang_Diep("cuteevcl"); 
    int T=1;// cin>>T;
    while(T--)
    {
        nhap();
        d__p::hoangdiep();
    }
    cerr<<"\nTime elapsed: "<<TIME<<".s\n";
    return 0;
}

Compilation message (stderr)

diameter.cpp: In member function 'void SegTree::update(int, int, int, int, int, ll)':
diameter.cpp:86:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |         int m=l+r>>1;
      |               ~^~
diameter.cpp: In member function 'll SegTree::get(int, int, int, int, int)':
diameter.cpp:101:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  101 |         int m=l+r>>1;
      |               ~^~
diameter.cpp: In function 'void d__p::solve()':
diameter.cpp:208:17: warning: unused variable 'w' [-Wunused-variable]
  208 |         int u,v,w,id;
      |                 ^
diameter.cpp:208:19: warning: unused variable 'id' [-Wunused-variable]
  208 |         int u,v,w,id;
      |                   ^~

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