oj.uz

Submission #858357

# Submission time Handle Problem Language Result Execution time Memory
858357 2023-10-08T08:32:54 Z alexdd Traffickers (RMI18_traffickers) C++17
100 / 100
 3459 ms 120808 KB 
#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--;
            long long 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);
                    if(cnt>0) rez += 1LL * cnt * 1LL* (max(0,(t2-r+d)/d) - max(0,(t1-r+d)/d));
                }
            }
            cout<<rez<<"\n";
        }
    }
    return 0;
}

Compilation message

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3312 KB Output is correct
2 Correct 11 ms 5468 KB Output is correct
3 Correct 14 ms 5576 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 59808 KB Output is correct
2 Correct 211 ms 59552 KB Output is correct
3 Correct 125 ms 60192 KB Output is correct
4 Correct 166 ms 60220 KB Output is correct
5 Correct 187 ms 59704 KB Output is correct
6 Correct 169 ms 59848 KB Output is correct
7 Correct 169 ms 59860 KB Output is correct
8 Correct 145 ms 59992 KB Output is correct
9 Correct 156 ms 60152 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1827 ms 119688 KB Output is correct
2 Correct 1487 ms 120440 KB Output is correct
3 Correct 1544 ms 120044 KB Output is correct
4 Correct 2735 ms 118964 KB Output is correct
5 Correct 3459 ms 118592 KB Output is correct
6 Correct 1620 ms 120332 KB Output is correct
7 Correct 1847 ms 120808 KB Output is correct
8 Correct 1878 ms 120224 KB Output is correct