Submission #1100882

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100882		modwwe	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	771 ms	80780 KiB

diameter

#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC optimize("conserve-stack")
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
#define getchar_unlocked getchar

inline int scan()
{
    char c = getchar_unlocked();
    int x = 0;
    while (c < '0' || c > '9')
    {
        c = getchar_unlocked();
    }
    while (c >= '0' && c <= '9')
    {
        x = (x << 1) + (x << 3) + c - '0';
        c = getchar_unlocked();
    }
    return x;
}

void phongbeo();
const int inf = 1e9;
const int mod2 = 1e9 + 7;
const int  mod1 = 998244353;
struct icd
{
    long double a;
    int b;
};
struct ib
{
    int a;
    int b;
};
struct ic
{
    int a, b, c;
};
struct id
{
    int a, b, c, d;
};
struct ie
{
    int a, b, c, d, e;

};

int n, m, s1, s2, s4, s3, sf, k, s5, s6, mx, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center;
int  i, s10, s12,k1,k2,k3,s11,t,limit,w,l,r,last,root;
int kk;
int el = 19;

main()
{
    if(fopen(task".inp","r"))
    {
        fin(task);
        fou(task);
    }
    NHP
    /// cin>>s1;
///modwwe
    phongbeo();
    // checktime
}
int dp[100001];
ic a[100001];
int head[100001];
int pos[100001];
int ou[100001];
vector<ib> v[100001];
vector<int> v2[100001];
int heavy[100001];
int c[100001];
int par[100001];
int pp[100001];
int ta[100001];
struct IT
{
    vector<int> t,t2,t3;
    int sz;
    void init(int x)
    {
        t.resize(x*4+1);
        t2.resize(x*4+1);
        t3.resize(x*4+1);
        sz=x;
    }
    void ff(int x)
    {
        for(int i=x*2; i<=x*2+1; i++)
            t2[i]+=t2[x],
                   t[i]+=t2[x];
        t2[x]=0;
    }
    void upd(int node,int l,int r,int l1,int x)
    {
        if(l==r)
        {
            t[node]=x;
            t[node]+=t2[node];
            t3[node]=pp[l];
            return;
        }
        int mid=l+r>>1;
        if(t2[node]!=0) ff(node);
        if(l1<=mid)
            upd(node<<1,l,mid,l1,x);
        else   upd(node<<1|1,mid+1,r,l1,x);
        t[node]=max(t[node<<1],t[node<<1|1]);
        if(t[node]==t[node<<1])t3[node]=t3[node<<1];
        else t3[node]=t3[node<<1|1];
    }
    void updhihi(int node,int l,int r,int l1,int x)
    {
        if(l==r)
        {
            t[node]=x;
            t3[node]=pp[l];
            return;
        }
        int mid=l+r>>1;
        if(t2[node]!=0) ff(node);
        if(l1<=mid)
            updhihi(node<<1,l,mid,l1,x);
        else   updhihi(node<<1|1,mid+1,r,l1,x);
        t[node]=max(t[node<<1],t[node<<1|1]);
        if(t[node]==t[node<<1])t3[node]=t3[node<<1];
        else t3[node]=t3[node<<1|1];
    }
    void upd2(int node,int l,int r,int l1,int r1,int x)
    {
        if(l>r1||r<l1) return;
        if(l>=l1&&r<=r1)
        {
            t[node]+=x;
            t2[node]+=x;
            return;
        }
        if(t2[node]!=0) ff(node);
        int mid=l+r>>1;
        upd2(node<<1,l,mid,l1,r1,x);
        upd2(node<<1|1,mid+1,r,l1,r1,x);
        t[node]=max(t[node<<1],t[node<<1|1]);
        if(t[node]==t[node<<1])t3[node]=t3[node<<1];
        else t3[node]=t3[node<<1|1];
    }
    int get(int node,int l,int r,int l1,int r1)
    {
        if(l1>r1) return -inf;
        if(l>r1||r<l1) return -inf;
        if(l>=l1&&r<=r1) return t[node];
        if(t2[node]!=0) ff(node);
        int mid=l+r>>1;
        return max(get(node<<1,l,mid,l1,r1),get(node<<1|1,mid+1,r,l1,r1));
    }
    void upd(int x,int y)
    {
        upd(1,1,sz,x,y);
    }
    void updhihi(int x,int y)
    {
        updhihi(1,1,sz,x,y);
    }
    void upd2(int x,int y,int z)
    {
        upd2(1,1,sz,x,y,z);
    }
    void upd2(int z)
    {
        upd2(1,1,sz,1,sz,z);
    }
    int get(int x)
    {
        return max(get(1,1,sz,1,x-1),get(1,1,sz,x+1,sz));
    }
} st[100001],seg,segtree;
struct fenwick_tree
{
    int bit[100001];
    void upd(int l,int r,int x)
    {
        for(l; l<=n; l+=l&-l)
            bit[l]+=x;
        for(r; r<=n; r+=r&-r)
            bit[r]-=x;
    }
    int get(int x)
    {
        int s=0;
        for(x; x; x-=x&-x)
            s+=bit[x];
        return s;
    }
} fen;
int dfs(int x,int y)
{
    int sz=1;
    int mxz=0;
    par[x]=y;
    for(auto f:v[x])
        if(f.a!=y)
        {
            dp[f.a]=dp[x]+f.b;
            int s=dfs(f.a,x);
            sz+=s;
            if(s>mxz)
                mxz=s,heavy[x]=f.a;
        }
    return sz;
}
void des(int x,int y)
{

    head[x]=y;
    pos[x]=++dem;
    pp[dem]=x;
    segtree.upd(pos[x],dp[x]);
    if(heavy[x]!=0)
    {
        des(heavy[x],y);
        c[heavy[x]]=0;

        dp[x]=max(dp[heavy[x]],dp[x]);
        v2[x].pb(heavy[x]);
    }
    int vitri=0;
    for(auto f:v[x])
    {
        if(!pos[f.a])
        {
            des(f.a,f.a);
            v2[x].pb(f.a);
            c[f.a]=++vitri;
            dp[x]=max(dp[f.a],dp[x]);
        }
    }
    ou[x]=dem;
}
void dfs2(int x)
{
    if(v2[x].size()!=0)
        st[x].init(v2[x].size()-1);
    int smx=0;
    for(auto f:v2[x])
    {
        if(f!=heavy[x])
            st[x].upd(c[f],dp[f]),smx=max(smx,dp[f]);
        dfs2(f);
    }
    for(auto f:v[x])
        if(par[x]!=f.a)
            fen.upd(pos[f.a],ou[f.a]+1,f.b),
                    seg.upd2(pos[f.a],ou[f.a],-f.b*2);
    seg.upd(pos[x],smx);
}
void dfs3(int x)
{
    ta[x]=fen.get(pos[x]);
    for(auto f:v2[x])
        dfs3(f);
}
void updout(int x,int y,int cost)
{
    if(c[y]==0) assert(0);
    int ss=fen.get(pos[x]);
    st[x].upd2(ss-ta[x]);
    st[x].updhihi(c[y],cost);
    ta[x]=ss;
    seg.updhihi(pos[x],st[x].t[1]-fen.get(pos[x])*2);
}
void upd_hld(int x,int y)
{
    if(head[x]==1) return;
    upd_hld(par[head[x]],y);
    y=segtree.get(1,1,n,pos[head[x]],ou[head[x]]);
    updout(par[head[x]],head[x],y);
}
int get_notheavy(int x,int y)
{
    if(c[y]==0) assert(0);
    return  max(st[x].get(c[y])-ta[x]+fen.get(pos[x]),
                segtree.get(1,1,n,pos[heavy[x]],ou[heavy[x]]))
            -fen.get(pos[x])*2;
}
bool check(int x)
{
    if(head[x]!=head[par[x]])return 1;
    return 0;
}
int tt(int x,bool f,int y)
{
    if(!f)    return seg.get(1,1,n,pos[head[x]],pos[x]);
    return  max(get_notheavy(x,y),seg.get(1,1,n,pos[head[x]],pos[par[x]]));
}
int get_hld(int x,bool f,int z)
{
    if(x==0) return 0;
    if(head[x]==1)return tt(x,f,z);
    return max({get_notheavy(par[head[x]],head[x]),
                tt(x,f,z),
                get_hld(par[par[head[x]]],check(par[head[x]]),par[head[x]]),0ll});
}
int deptrai(int x)
{
    if(par[a[x].b]==a[x].a) return a[x].b;
    return a[x].a;
}
int xuli(int x,int y)
{
    s3=deptrai(x);
    s4=y-a[x].c;
    a[x].c=y;
    fen.upd(pos[s3],ou[s3]+1,s4);
    segtree.upd2(pos[s3],ou[s3],s4);
    seg.upd2(pos[s3],ou[s3],-s4);
    upd_hld(s3,segtree.get(1,1,n,pos[s3],ou[s3]));
    return segtree.t3[1];
}
int get(int x)
{
    return max(0ll,get_hld(par[x],check(x),x))+segtree.t[1];
}
void phongbeo()
{
    cin>>n>>m>>limit;
    for(int i=1; i<n; i++)
    {
        cin>>l>>r>>t;
        v[l].pb({r,t});
        v[r].pb({l,t});
        a[i]= {l,r,t};
    }
    dfs(1,0) ;
    seg.init(n);
    segtree.init(n);
    des(1,1);
    dfs2(1);
    dfs3(1);
    last=0;

    for(int i=1; i<=m; i++)
    {
        cin>>l>>r;
        l=(l+last)%(n-1)+1;
        r=(r+last)%limit;
        root=xuli(l,r);
        last=get(root);
        cout<<last;
        //debug
        down
    }
}

Compilation message (stderr)

diameter.cpp:69:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   69 | main()
      | ^~~~
diameter.cpp: In member function 'void IT::upd(long long int, long long int, long long int, long long int, long long int)':
diameter.cpp:121:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  121 |         int mid=l+r>>1;
      |                 ~^~
diameter.cpp: In member function 'void IT::updhihi(long long int, long long int, long long int, long long int, long long int)':
diameter.cpp:138:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  138 |         int mid=l+r>>1;
      |                 ~^~
diameter.cpp: In member function 'void IT::upd2(long long int, long long int, long long int, long long int, long long int, long long int)':
diameter.cpp:157:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  157 |         int mid=l+r>>1;
      |                 ~^~
diameter.cpp: In member function 'long long int IT::get(long long int, long long int, long long int, long long int, long long int)':
diameter.cpp:170:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  170 |         int mid=l+r>>1;
      |                 ~^~
diameter.cpp: In member function 'void fenwick_tree::upd(long long int, long long int, long long int)':
diameter.cpp:199:13: warning: statement has no effect [-Wunused-value]
  199 |         for(l; l<=n; l+=l&-l)
      |             ^
diameter.cpp:201:13: warning: statement has no effect [-Wunused-value]
  201 |         for(r; r<=n; r+=r&-r)
      |             ^
diameter.cpp: In member function 'long long int fenwick_tree::get(long long int)':
diameter.cpp:207:13: warning: statement has no effect [-Wunused-value]
  207 |         for(x; x; x-=x&-x)
      |             ^
diameter.cpp: In function 'int main()':
diameter.cpp:13:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define fin(x) freopen(x".inp","r",stdin)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~
diameter.cpp:73:9: note: in expansion of macro 'fin'
   73 |         fin(task);
      |         ^~~
diameter.cpp:14:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 | #define fou(x) freopen(x".out","w",stdout)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~
diameter.cpp:74:9: note: in expansion of macro 'fou'
   74 |         fou(task);
      |         ^~~

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