Submission #476615

# Submission time Handle Problem Language Result Execution time Memory
476615 2021-09-27T19:14:49 Z stefantaga Traffickers (RMI18_traffickers) C++14
90 / 100
3500 ms 223708 KB
#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)
        {
            for (int t=j;t<i;t++)
            {
                arb[i][t][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);
        }
        for (int t=0;t<i;t++)
        {
            arb[i][t][nod]=arb[i][t][2*nod]+arb[i][t][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,grupecomplete,gruperamase;
    long long suma=0,numar=0;
    if (timp<0)
    {
        return 0;
    }
    for (i=1; i<=20; i++)
    {
        grupecomplete=timp/i;
        suma=(suma+1LL*catesunt(x,y,i,i-1)*grupecomplete);
        gruperamase=timp%i;
        suma=(suma+1LL*catesunt(x,y,i,gruperamase));
    }
    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

traffickers.cpp: In function 'void dfs(int, int)':
traffickers.cpp:76:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for (int i=0; i<v[x].size(); i++)
      |                   ~^~~~~~~~~~~~
traffickers.cpp: In function 'void construieste(int, int)':
traffickers.cpp:105:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     for (int i=0; i<v[x].size(); i++)
      |                   ~^~~~~~~~~~~~
traffickers.cpp: In function 'long long int rasp(int, int, int)':
traffickers.cpp:199:11: warning: unused variable 'j' [-Wunused-variable]
  199 |     int i,j,grupecomplete,gruperamase;
      |           ^
traffickers.cpp:200:22: warning: unused variable 'numar' [-Wunused-variable]
  200 |     long long suma=0,numar=0;
      |                      ^~~~~
# Verdict Execution time Memory Grader output
1 Correct 2 ms 2892 KB Output is correct
2 Correct 14 ms 6516 KB Output is correct
3 Correct 16 ms 9516 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 203 ms 58948 KB Output is correct
2 Correct 210 ms 65468 KB Output is correct
3 Correct 276 ms 43080 KB Output is correct
4 Correct 206 ms 63656 KB Output is correct
5 Correct 226 ms 70824 KB Output is correct
6 Correct 221 ms 67396 KB Output is correct
7 Correct 236 ms 61792 KB Output is correct
8 Correct 177 ms 43980 KB Output is correct
9 Correct 186 ms 40764 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3366 ms 185880 KB Output is correct
2 Correct 3106 ms 150276 KB Output is correct
3 Execution timed out 3570 ms 130856 KB Time limit exceeded
4 Correct 2032 ms 219896 KB Output is correct
5 Correct 1769 ms 223708 KB Output is correct
6 Execution timed out 3573 ms 137028 KB Time limit exceeded
7 Correct 2996 ms 117236 KB Output is correct
8 Correct 3213 ms 118192 KB Output is correct