Submission #498037

#	Time	Username	Problem	Language	Result	Execution time	Memory
498037		andrei_boaca	Dynamic Diameter (CEOI19_diameter)	C++14	0 / 100	371 ms	234492 KiB

diameter

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
pii G[100005];
ll n,q,w,weight[100005],root,nr[100005],niv[100005],timp,in[100005],out[100005],parent[100005],ans;
int lg[100005];
vector<pii> muchii[100005];
struct interv
{
    ll root,st,dr;
};
vector<interv> where[100005];
multiset<ll> setik;
bool use[100005];
struct date
{
    ll val,st,dr;
};
vector<date> arb[100005],linie[100005];
vector<ll> toprop[100005];
vector<ll> edge;
vector<ll> tree;
int nvm[100005];
void build(ll index,ll nod,ll st,ll dr)
{
    if(st>dr)
        return;
    if(st==dr)
    {
        if(index==10)
        {
            ll x=linie[index][st].st;
            ll y=linie[index][st].dr;
            ll pp=linie[index][st].val;
            ll z=x;
        }
        arb[index][nod].st=linie[index][st].st;
        arb[index][nod].dr=linie[index][st].dr;
        return;
    }
    int mij=(st+dr)/2;
    build(index,nod*2,st,mij);
    build(index,nod*2+1,mij+1,dr);
    arb[index][nod].st=arb[index][nod*2].st;
    arb[index][nod].dr=arb[index][nod*2].dr;
}
void prop(ll index,ll nod)
{
    ll val=toprop[index][nod];
    for(int i=nod*2;i<=nod*2+1;i++)
    {
        arb[index][i].val+=val;
        toprop[index][i]+=val;
    }
}
void update(ll index,ll nod,ll st,ll dr,ll a, ll b, ll val)
{
    if(st!=dr)
        prop(index,nod);
    toprop[index][nod]=0;
    if(st>=a&&dr<=b)
    {
        arb[index][nod].val+=val;
        toprop[index][nod]+=val;
        return;
    }
    int mij=(st+dr)/2;
    if(a<=mij)
        update(index,nod*2,st,mij,a,b,val);
    if(b>mij)
        update(index,nod*2+1,mij+1,dr,a,b,val);
    arb[index][nod].val=max(arb[index][nod*2].val,arb[index][nod*2+1].val);
    if(arb[index][nod].val==arb[index][nod*2].val)
    {
        arb[index][nod].st=arb[index][nod*2].st;
        arb[index][nod].dr=arb[index][nod*2].dr;
    }
    else
    {
        arb[index][nod].st=arb[index][nod*2+1].st;
        arb[index][nod].dr=arb[index][nod*2+1].dr;
    }
}
date query(ll index,ll nod,ll st,ll dr,ll a,ll b)
{
    if(a>b||st>dr)
        return {0,0,0};
    if(st!=dr)
        prop(index,nod);
    toprop[index][nod]=0;
    if(st>=a&&dr<=b)
        return arb[index][nod];
    int mij=(st+dr)/2;
    date x={0,0,0},y={0,0,0};
    if(a<=mij)
        x=query(index,nod*2,st,mij,a,b);
    if(b>mij)
        y=query(index,nod*2+1,mij+1,dr,a,b);
    if(x.val>y.val)
        return x;
    else
        return y;
}
void dfs(int nod,int par)
{
    nr[nod]=1;
    parent[nod]=par;
    for(int i=0;i<muchii[nod].size();i++)
    {
        int fiu=muchii[nod][i].first;
        if(fiu!=par&&!use[fiu])
        {
            edge.push_back(muchii[nod][i].second);
            dfs(fiu,nod);
            nr[nod]+=nr[fiu];
        }
    }
}
void liniarize(int nod,int par,int root)
{
    timp++;
    in[nod]=timp;
    if(nod!=root)
    {
        if(par==root)
            nvm[nod]=nod;
        else
            nvm[nod]=nvm[par];
    }
    else
        nvm[nod]=nod;
    tree.push_back(nod);
    if(nod==root)
        niv[nod]=1;
    for(int i=0;i<muchii[nod].size();i++)
    {
        int fiu=muchii[nod][i].first;
        if(!use[fiu]&&fiu!=par)
        {
            niv[fiu]=niv[nod]+1;
            liniarize(fiu,nod,root);
        }
    }
    out[nod]=timp;
}
int centroid(ll nod)
{
    edge.clear();
    dfs(nod,0);
    ll sz=nr[nod];
    if(sz==1)
        return nod;
    while(true)
    {
        bool ok=1;
        for(int i=0;i<muchii[nod].size();i++)
        {
            int fiu=muchii[nod][i].first;
            if(fiu!=parent[nod]&&!use[fiu])
                if(nr[fiu]>sz/2)
                {
                    ok=0;
                    parent[nod]=fiu;
                    parent[fiu]=0;
                    nr[nod]-=nr[fiu];
                    nr[fiu]=sz;
                    nod=fiu;
                    break;
                }
        }
        if(!ok)
            continue;
        else
            break;
    }
    bool good=0;
    if(nod==10LL)
        good=1;
    tree.clear();
    timp=0;
    liniarize(nod,0,nod);
    linie[nod].resize(sz+1);
    for(int i:tree)
    {
        int st=in[nvm[i]],dr=out[nvm[i]];
        linie[nod][in[i]]={i,st,dr};
    }
    arb[nod].resize(5*sz+5);
    toprop[nod].resize(5*sz+5);
    use[nod]=1;
    lg[nod]=sz;
    for(int i=0;i<edge.size();i++)
    {
        interv x;
        x.root=nod;
        ll e=edge[i];
        ll a=G[e].first,b=G[e].second;
        if(niv[a]<niv[b])
            swap(a,b);
        x.st=in[a];
        x.dr=out[a];
        where[e].push_back(x);
    }
    for(int i=0;i<muchii[nod].size();i++)
    {
        int fiu=muchii[nod][i].first;
        if(!use[fiu])
            centroid(fiu);
    }
}
ll calcbest(ll i)
{
    date x=query(i,1,1,lg[i],1,lg[i]);
    ll suma=x.val;
    date a1=query(i,1,1,lg[i],1,x.st-1);
    date a2=query(i,1,1,lg[i],x.dr+1,lg[i]);
    suma+=max(a1.val,a2.val);
    return suma;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>q>>w;
    for(int i=1;i<n;i++)
    {
        ll a,b,c;
        cin>>a>>b>>c;
        muchii[a].push_back({b,i});
        muchii[b].push_back({a,i});
        weight[i]=c;
        G[i]={a,b};
    }
    root=centroid(1);
    for(int i=1;i<=n;i++)
    {
        bool vv=0;
        if(i==10)
            vv=1;
        build(i,1,1,lg[i]);
    }
    for(int i=1;i<n;i++)
        for(int j=0;j<where[i].size();j++)
        {
            ll st=where[i][j].st;
            ll dr=where[i][j].dr;
            ll index=where[i][j].root;
            update(index,1,1,lg[index],st,dr,weight[i]);
            /*if(index==10)
                cout<<arb[index][1].st<<' '<<arb[index][1].dr<<'\n';*/
        }
    for(int i=1;i<=n;i++)
        if(arb[i].size()>=2)
        {
            ll suma=calcbest(i);
            setik.insert(suma);
        }
    ans=*prev(setik.end());
    ll last=0;
    while(q--)
    {
        ll d,e;
        cin>>d>>e;
        d=(d+last)%(n-1)+1;
        e=(e+last)%w;
        ll dif=e-weight[d];
        weight[d]+=dif;
        for(int j=0;j<where[d].size();j++)
        {
            ll st=where[d][j].st;
            ll dr=where[d][j].dr;
            ll index=where[d][j].root;
            ll suma=calcbest(index);
            setik.erase(setik.find(suma));
            update(index,1,1,lg[index],st,dr,dif);
            suma=calcbest(index);
            setik.insert(suma);
        }
        ans=*prev(setik.end());
        cout<<ans<<'\n';
        last=ans;
    }
    return 0;
}

Compilation message (stderr)

diameter.cpp: In function 'void build(ll, ll, ll, ll)':
diameter.cpp:36:16: warning: unused variable 'y' [-Wunused-variable]
   36 |             ll y=linie[index][st].dr;
      |                ^
diameter.cpp:37:16: warning: unused variable 'pp' [-Wunused-variable]
   37 |             ll pp=linie[index][st].val;
      |                ^~
diameter.cpp:38:16: warning: unused variable 'z' [-Wunused-variable]
   38 |             ll z=x;
      |                ^
diameter.cpp: In function 'void dfs(int, int)':
diameter.cpp:111:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     for(int i=0;i<muchii[nod].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~~~
diameter.cpp: In function 'void liniarize(int, int, int)':
diameter.cpp:138:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |     for(int i=0;i<muchii[nod].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~~~
diameter.cpp: In function 'int centroid(ll)':
diameter.cpp:159:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |         for(int i=0;i<muchii[nod].size();i++)
      |                     ~^~~~~~~~~~~~~~~~~~~
diameter.cpp:195:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  195 |     for(int i=0;i<edge.size();i++)
      |                 ~^~~~~~~~~~~~
diameter.cpp:207:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  207 |     for(int i=0;i<muchii[nod].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~~~
diameter.cpp:179:10: warning: variable 'good' set but not used [-Wunused-but-set-variable]
  179 |     bool good=0;
      |          ^~~~
diameter.cpp: In function 'int main()':
diameter.cpp:240:14: warning: variable 'vv' set but not used [-Wunused-but-set-variable]
  240 |         bool vv=0;
      |              ^~
diameter.cpp:246:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<interv>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  246 |         for(int j=0;j<where[i].size();j++)
      |                     ~^~~~~~~~~~~~~~~~
diameter.cpp:271:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<interv>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  271 |         for(int j=0;j<where[d].size();j++)
      |                     ~^~~~~~~~~~~~~~~~
diameter.cpp: In function 'int centroid(ll)':
diameter.cpp:213:1: warning: control reaches end of non-void function [-Wreturn-type]
  213 | }
      | ^

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