Submission #476609

#	Time	Username	Problem	Language	Result	Execution time	Memory
476609		stefantaga	Traffickers (RMI18_traffickers)	C++14	60 / 100	3606 ms	223660 KiB

traffickers

#include <bits/stdc++.h>

using namespace std;
class SegTree
{
    int *arb[21][22];
public:
    void Initialize(int lung)
    {
        int i,j;
        for (i=1; i<=20; i++)
        {
            for (j=0; j<=i; j++)
            {
                arb[i][j]= new int [(4*lung+1)];
                for (int t=0; t<=4*lung; t++)
                {
                    arb[i][j][t]=0;
                }
            }
        }
    }
    void update(int st,int dr,int nod,int poz,int val,int i,int j)
    {
        if (st>dr)
        {
            return;
        }
        if (st==dr)
        {
            arb[i][j][nod]+=val;
            return;
        }
        int mij=(st+dr)/2;
        if (poz<=mij)
        {
            update(st,mij,2*nod,poz,val,i,j);
        }
        else
        {
            update(mij+1,dr,2*nod+1,poz,val,i,j);
        }
        arb[i][j][nod]=arb[i][j][2*nod]+arb[i][j][2*nod+1];
    }
    int query(int st,int dr,int nod,int ua,int ub,int i,int j)
    {
        if (ua<=st&&dr<=ub)
        {
            return arb[i][j][nod];
        }
        int mij=(st+dr)/2,sum=0;
        if (ua<=mij)
        {
            sum=sum+query(st,mij,2*nod,ua,ub,i,j);
        }
        if (mij<ub)
        {
            sum=sum+query(mij+1,dr,2*nod+1,ua,ub,i,j);
        }
        return sum;
    }
}*ceam;
int tata[100005],niv[100005],mar[100005],poz[100005],lung[100005],id[100005],prim[100005],max_fiu[100005];
vector <int> v[100005];
void dfs(int x,int t)
{
    tata[x]=t;
    mar[x]=1;
    niv[x]=niv[t]+1;
    for (int i=0; i<v[x].size(); i++)
    {
        int nod=v[x][i];
        if (v[x][i]!=t)
        {
            dfs(v[x][i],x);
            mar[x]+=mar[nod];
            if (mar[nod]>mar[max_fiu[x]])
            {
                max_fiu[x]=nod;
            }
        }
    }
}
int q;
void construieste(int x,int t)
{
    ++lung[q];
    poz[x]=lung[q];
    if (lung[q]==1)
    {
        prim[q]=x;
    }
    id[x]=q;
    if (mar[x]==1)
    {
        return;
    }
    construieste(max_fiu[x],x);
    for (int i=0; i<v[x].size(); i++)
    {
        if (v[x][i]!=tata[x]&&v[x][i]!=max_fiu[x])
        {
            q++;
            construieste(v[x][i],x);
        }

    }
}
int rmq[100005][20],lg;
int lca(int x,int y)
{
    if (niv[x]<niv[y])
    {
        return lca(y,x);
    }
    int dif=niv[x]-niv[y];
    for (int i=0; i<=lg; i++)
    {
        if ((dif&(1<<i)))
        {
            x=rmq[x][i];
        }
    }
    if (x!=y)
    {
        for (int i=lg; i>=0; i--)
        {
            if (rmq[x][i]!=rmq[y][i])
            {
                x=rmq[x][i];
                y=rmq[y][i];
            }
        }
        x=rmq[x][0];
    }
    return x;
}
void updatetrafic(int x,int y,int valoare)
{
    int salut,lungime,nr;
    salut=lca(x,y);
    lungime=niv[x]+niv[y]-2*niv[salut]+1;
    nr=0;
    while (x!=tata[salut])
    {
        ceam[id[x]].update(1,lung[id[x]],1,poz[x],valoare,lungime,nr);
        ceam[id[x]].update(1,lung[id[x]],1,poz[x],valoare,lungime,lungime);
        nr++;
        x=tata[x];
    }
    nr=lungime-1;
    x=y;
    while (x!=salut)
    {
        ceam[id[x]].update(1,lung[id[x]],1,poz[x],valoare,lungime,nr);
        ceam[id[x]].update(1,lung[id[x]],1,poz[x],valoare,lungime,lungime);
        nr--;
        x=tata[x];
    }
}
int min1(int x,int y)
{
    if (x>y)
    {
        return y;
    }
    return x;
}
int max1(int x,int y)
{
    if (x<y)
    {
        return y;
    }
    return x;
}
long long catesunt(int x,int y,int i,int j)
{
    if (id[x]==id[y])
    {
        int st=min1(poz[x],poz[y]);
        int dr=max1(poz[x],poz[y]);
        return ceam[id[x]].query(1,lung[id[x]],1,st,dr,i,j);
    }
    if (niv[prim[id[x]]]>niv[prim[id[y]]])
    {
        swap(x,y);
    }
    return catesunt(y,prim[id[y]],i,j)+catesunt(tata[prim[id[y]]],x,i,j);
}
long long rasp(int x,int y,int timp)
{
    int i,j;
    long long suma=0,numar=0;
    if (timp<0)
    {
        return 0;
    }
    for (i=1; i<=20; i++)
    {
        if (catesunt(x,y,i,i)!=0)
        {
            for (j=0; j<i; j++)
            {
                if (timp<j)
                {
                    numar=0;
                }
                else
                {
                    numar=(timp-j)/i+1;
                }
                suma=suma+(1LL*catesunt(x,y,i,j)*numar);
            }
        }
    }
    return suma;
}
int n,x,i,j,y,queryuri,tip,t1,t2;
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
#ifdef HOME
    ifstream cin("date.in");
    ofstream cout("date.out");
#endif // HOME
    cin>>n;
    for (i=1; i<n; i++)
    {
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    q=1;
    dfs(1,0);
    for (i=1; i<=n; i++)
    {
        rmq[i][0]=tata[i];
    }
    lg=log2(n);
    for (i=1; i<=lg; i++)
    {
        for (j=1; j<=n; j++)
        {
            rmq[j][i]=rmq[rmq[j][i-1]][i-1];
        }
    }
    construieste(1,0);
    ceam= new SegTree [(q+1)];
    for (i=1; i<=q; i++)
    {
        ceam[i].Initialize(lung[i]);
    }
    int traficanti;
    cin>>traficanti;
    for (i=1; i<=traficanti; i++)
    {
        cin>>x>>y;
        updatetrafic(x,y,1);
    }
    cin>>queryuri;
    for (int t=1; t<=queryuri; t++)
    {
        cin>>tip;
        if (tip==1)
        {
            cin>>x>>y;
            updatetrafic(x,y,1);
        }
        else if (tip==2)
        {
            cin>>x>>y;
            updatetrafic(x,y,-1);
        }
        else
        {
            cin>>x>>y>>t1>>t2;
            cout<<rasp(x,y,t2)-rasp(x,y,t1-1)<<'\n';
        }
    }
    return 0;
}

Compilation message (stderr)

traffickers.cpp: In function 'void dfs(int, int)':
traffickers.cpp:70:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for (int i=0; i<v[x].size(); i++)
      |                   ~^~~~~~~~~~~~
traffickers.cpp: In function 'void construieste(int, int)':
traffickers.cpp:99:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     for (int i=0; i<v[x].size(); i++)
      |                   ~^~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 0 / 40