oj.uz

Submission #1088887

# Submission time Handle Problem Language Result Execution time Memory
1088887 2024-09-15T13:05:35 Z ASN49K Traffickers (RMI18_traffickers) C++14
100 / 100
 1220 ms 59992 KB 
#include <bits/stdc++.h>
using namespace std;
using i64=long long;
#define int 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;
}
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++)
                {
                    rez+=1LL*paths[j][i].query(x,y)*((t2/i)+((t2%i)>=j));
                }
            }
            if(t1>=0)
            {
                for(int i=1;i<=MAX_LEN_PATH;i++)
                {
                    for(int j=0;j<i;j++)
                    {
                        rez-=1LL*paths[j][i].query(x,y)*((t1/i)+((t1%i)>=j));
                    }
                }
            }
            cout<<rez<<'\n';
        }
    }
}

Compilation message

traffickers.cpp:145:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  145 | main()
      | ^~~~

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 2908 KB Output is correct
3 Correct 4 ms 2904 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 19992 KB Output is correct
2 Correct 67 ms 18100 KB Output is correct
3 Correct 55 ms 19248 KB Output is correct
4 Correct 75 ms 20056 KB Output is correct
5 Correct 60 ms 19800 KB Output is correct
6 Correct 66 ms 20048 KB Output is correct
7 Correct 56 ms 19544 KB Output is correct
8 Correct 53 ms 20052 KB Output is correct
9 Correct 45 ms 20060 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1006 ms 59512 KB Output is correct
2 Correct 1110 ms 59992 KB Output is correct
3 Correct 1124 ms 59616 KB Output is correct
4 Correct 1220 ms 59180 KB Output is correct
5 Correct 1139 ms 58844 KB Output is correct
6 Correct 1075 ms 59768 KB Output is correct
7 Correct 790 ms 59988 KB Output is correct
8 Correct 830 ms 59656 KB Output is correct