oj.uz

Submission #1088888

# Submission time Handle Problem Language Result Execution time Memory
1088888 2024-09-15T13:09:05 Z ASN49K Traffickers (RMI18_traffickers) C++14
100 / 100
 541 ms 32732 KB 
#include <bits/stdc++.h>
using namespace std;
using i64=long long;
#define UNUSED -1
#define all(x) x.begin(),x.end()
#define pb push_back
const int mod=1e9+7;
struct Aib
{
    int n;
    vector<int>aib;
    int lsb(int x)
    {
        return x&(-x);
    }
    void update(int poz,int val)
    {
        for(;poz<=n;poz+=lsb(poz))
        {
            aib[poz]+=val;
        }
    }
    int query(int poz)
    {
        int rez=0;
        for(;poz>0;poz-=lsb(poz))
        {
            rez+=aib[poz];
        }
        return rez;
    }
    void init(int n)
    {
        this->n=n;
        aib.assign(n+1,0);
    }
};
const int N=30'000,LG=15;
const int MAX_LEN_PATH=20;

int n;
int tin[N],tout[N],p[N],tt[LG+1][N];
vector<int>adj[N];

void dfs(int nod,int tt)
{
    static int timp=0;
    tin[nod]=++timp;
    p[nod]=tt;
    for(auto &c:adj[nod])
    {
        if(c!=tt)
        {
            dfs(c,nod);
        }
    }
    tout[nod]=timp;
}
void build()
{
    for(int i=0;i<n;i++)
    {
        tt[0][i]=p[i];
    }
    for(int i=1;i<=LG;i++)
    {
        for(int j=0;j<n;j++)
        {
            tt[i][j]=tt[i-1][tt[i-1][j]];
        }
    }
}
bool is_parent(int x,int y)
{
    return (tin[x]<=tin[y] && tout[y]<=tout[x]);
}
int get_lca(int x,int y)
{
    if(is_parent(x,y))
    {
        return x;
    }
    if(is_parent(y,x))
    {
        return y;
    }
    for(int i=LG;i>=0;i--)
    {
        if(!is_parent(tt[i][x],y))
        {
            x=tt[i][x];
        }
    }
    return p[x];
}


struct path_querys
{
    Aib aib;
    void init()
    {
        aib.init(n);
    }
    void add(int nod,int semn)
    {
        aib.update(tin[nod] , semn);
        aib.update(tout[nod]+1 , -semn);
    }
    int query(int x,int y)
    {
        int lca=get_lca(x,y);
        int now=aib.query(tin[x])+aib.query(tin[y])-aib.query(tin[lca]);
        if(lca!=0)
        {
            now-=aib.query(tin[p[lca]]);
        }
        return now;
    }
}paths[MAX_LEN_PATH][MAX_LEN_PATH+1];

vector<int> get_path(int x,int y)
{
    int lca=get_lca(x,y);
    vector<int>a,b;
    while(x!=lca)
    {
        a.pb(x);
        x=p[x];
    }
    a.pb(lca);
    while(y!=lca)
    {
        b.pb(y);
        y=p[y];
    }
    reverse(all(b));
    for(auto &c:b)
    {
        a.pb(c);
    }
    return a;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin>>n;
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        x--;
        y--;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    dfs(0,0);
    build();
    for(int i=1;i<=MAX_LEN_PATH;i++)
    {
        for(int j=0;j<i;j++)
        {
            paths[j][i].init();
        }
    }

    int k;
    cin>>k;
    for(int i=0;i<k;i++)
    {
        int x,y;
        cin>>x>>y;
        x--;
        y--;
        auto v=get_path(x,y);
        int len=(int)v.size();
        for(int i=0;i<len;i++)
        {
            paths[i][len].add(v[i],1);
        }
    }

    int q;
    cin>>q;
    while(q--)
    {
        int cer,x,y;
        cin>>cer>>x>>y;
        x--;
        y--;
        if(cer==1)
        {
            auto v=get_path(x,y);
            int len=(int)v.size();
            for(int i=0;i<len;i++)
            {
                paths[i][len].add(v[i],1);
            }
        }
        else if(cer==2)
        {
            auto v=get_path(x,y);
            int len=(int)v.size();
            for(int i=0;i<len;i++)
            {
                paths[i][len].add(v[i],-1);
            }
        }
        else
        {
            int t1,t2;
            cin>>t1>>t2;
            t1--;
            i64 rez=0;
            for(int i=1;i<=MAX_LEN_PATH;i++)
            {
                for(int j=0;j<i;j++)
                {
                    int vv=paths[j][i].query(x,y);
                    rez+=1LL*vv*((t2/i)+(j<=(t2%i)));
                    if(t1>=0)
                    {
                        rez-=1LL*vv*((t1/i)+(j<=(t1%i)));
                    }
                }
            }
            cout<<rez<<'\n';
        }
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 3 ms 2140 KB Output is correct
3 Correct 3 ms 2140 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 10840 KB Output is correct
2 Correct 33 ms 9820 KB Output is correct
3 Correct 35 ms 10584 KB Output is correct
4 Correct 37 ms 11072 KB Output is correct
5 Correct 39 ms 10844 KB Output is correct
6 Correct 35 ms 10840 KB Output is correct
7 Correct 34 ms 10840 KB Output is correct
8 Correct 38 ms 10924 KB Output is correct
9 Correct 30 ms 11096 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 512 ms 32128 KB Output is correct
2 Correct 541 ms 32596 KB Output is correct
3 Correct 501 ms 32336 KB Output is correct
4 Correct 479 ms 31824 KB Output is correct
5 Correct 535 ms 31572 KB Output is correct
6 Correct 485 ms 32592 KB Output is correct
7 Correct 341 ms 32732 KB Output is correct
8 Correct 352 ms 32476 KB Output is correct