Submission #858351

#	Time	Username	Problem	Language	Result	Execution time	Memory
858351		alexdd	Traffickers (RMI18_traffickers)	C++17	15 / 100	3020 ms	122896 KiB

traffickers

#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> con[30005];
int parent[30005];
int depth[30005];
int head[30005];
int heavy[30005];
int siz[30005];
int pos[30005], curpos;
int tin[30005];
int tout[30005];
int timer;

int aint[120100][21][21];
void upd(int nod, int st, int dr, int poz, int newv, int x, int y)
{
    if(st==dr)
    {
        aint[nod][x][y]+=newv;
        return;
    }
    int mij=(st+dr)/2;
    if(poz<=mij) upd(nod*2,st,mij,poz,newv,x,y);
    else upd(nod*2+1,mij+1,dr,poz,newv,x,y);
    aint[nod][x][y] = aint[nod*2][x][y] + aint[nod*2+1][x][y];
}
int qry(int nod, int st, int dr, int le, int ri, int x, int y)
{
    if(le>ri)
        return 0;
    if(le==st && dr==ri)
        return aint[nod][x][y];
    int mij=(st+dr)/2;
    return qry(nod*2,st,mij,le,min(mij,ri),x,y)+
           qry(nod*2+1,mij+1,dr,max(mij+1,le),ri,x,y);
}

bool isanc(int x, int y)
{
    if(tin[x]<=tin[y] && tout[x]>=tout[y])
        return 1;
    return 0;
}
void dfs_init(int nod)
{
    heavy[nod]=-1;
    siz[nod]=1;
    tin[nod]=++timer;
    int maxc=0;
    for(auto adj:con[nod])
    {
        if(adj!=parent[nod])
        {
            depth[adj]=depth[nod]+1;
            parent[adj]=nod;
            dfs_init(adj);
            siz[nod]+=siz[adj];
            if(siz[adj]>maxc)
                maxc=siz[adj], heavy[nod]=adj;
        }
    }
    tout[nod]=++timer;
}
void decompose(int nod, int chead)
{
    pos[nod]=++curpos;
    head[nod]=chead;
    if(heavy[nod]!=-1)
        decompose(heavy[nod], chead);
    for(auto adj:con[nod])
        if(adj!=parent[nod] && adj!=heavy[nod])
            decompose(adj, adj);
}
int qry_hld(int a, int b, int x, int y)
{
    int rez=0;
    for(;head[a]!=head[b];b=parent[head[b]])
    {
        if(depth[head[a]]>depth[head[b]])
            swap(a,b);
        rez += qry(1,1,n,pos[head[b]],pos[b],x,y);
    }
    if(pos[b]>pos[a])
        swap(a,b);
    rez += qry(1,1,n,pos[b],pos[a],x,y);
    return rez;
}
void init_hld()
{
    dfs_init(1);
    decompose(1,1);
}
void doupd(int x, int y, int newv)
{
    vector<int> v;
    vector<int> v2;
    while(!isanc(x,y))
    {
        v.push_back(x);
        x = parent[x];
    }
    v.push_back(x);
    while(y!=x)
    {
        v2.push_back(y);
        y = parent[y];
    }
    int lun = (int)v.size() + (int)v2.size();
    int cnt=0;
    for(int i=0;i<v.size();i++)
    {
        upd(1,1,n,pos[v[i]],newv,lun,cnt);
        cnt++;
    }
    for(int i=(int)v2.size()-1;i>=0;i--)
    {
        upd(1,1,n,pos[v2[i]],newv,lun,cnt);
        cnt++;
    }
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    int a,b;
    for(int i=1;i<n;i++)
    {
        cin>>a>>b;
        con[a].push_back(b);
        con[b].push_back(a);
    }
    init_hld();
    int cntk,cntq,tip,t1,t2;
    cin>>cntk;
    for(int i=0;i<cntk;i++)
    {
        cin>>a>>b;
        doupd(a,b,1);
    }
    cin>>cntq;
    for(int i=0;i<cntq;i++)
    {
        cin>>tip;
        if(tip==1)
        {
            cin>>a>>b;
            doupd(a,b,1);
        }
        else if(tip==2)
        {
            cin>>a>>b;
            doupd(a,b,-1);
        }
        else
        {
            cin>>a>>b>>t1>>t2;
            t1--;
            int rez=0;
            for(int d=1;d<=20;d++)
            {
                for(int r=0;r<d;r++)
                {
                    int cnt = qry_hld(a,b,d,r);
                    rez += cnt * (max(0,(t2-r+d)/d) - max(0,(t1-r+d)/d));
                }
            }
            cout<<rez<<"\n";
        }
    }
    return 0;
}

Compilation message (stderr)

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

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