oj.uz

Submission #642013

# Submission time Handle Problem Language Result Execution time Memory
642013 2022-09-18T09:27:40 Z Tenis0206 Traffickers (RMI18_traffickers) C++11
100 / 100
 1755 ms 56696 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

int n,k,q;

vector<int> G[30005];

int w[30005],Max[30005],lvl[30005],l[30005],poz[30005],t[30005],c[30005];

int cnt = 0, paths = 1;

void get_w(int nod, int dad = 0)
{
    w[nod] = 1;
    for(auto it : G[nod])
    {
        if(it==dad)
        {
            continue;
        }
        get_w(it,nod);
        w[nod] += w[it];
        t[it] = nod;
        if(w[it] > w[Max[nod]])
        {
            Max[nod] = it;
        }
    }
}

void get_paths(int nod, int dad = 0, int level = 1)
{
    lvl[nod] = level;
    poz[nod] = (++cnt);
    l[nod] = paths;
    if(G[nod].size()==1 && nod!=1)
    {
        return;
    }
    get_paths(Max[nod],nod,level+1);
    for(auto it : G[nod])
    {
        if(it==dad || it==Max[nod])
        {
            continue;
        }
        ++paths;
        c[paths] = it;
        get_paths(it,nod,level+1);
    }
}

int aib[25][25][300005];

int ub(int x)
{
    return (x & (-x));
}

void update(int poz, int d, int r, int val)
{
    ++r;
    for(int i=poz; i<=n; i+=ub(i))
    {
        for(int j=r; j<=d; j+=ub(j))
        {
            aib[d][j][i] += val;
        }
    }
}

int query(int tp, int poz)
{
    int rez = 0;
    for(int d=1; d<=20; d++)
    {
        for(int i=poz; i>=1; i-=ub(i))
        {
            int r = tp % d;
            ++r;
            for(int j=r;j>=1;j-=ub(j))
            {
                rez += 1LL * aib[d][j][i] * (tp / d + 1);
            }
            for(int j=d;j>=1;j-=ub(j))
            {
                rez += 1LL * aib[d][j][i] * (tp / d);
            }
            for(int j=r;j>=1;j-=ub(j))
            {
                rez -= 1LL * aib[d][j][i] * (tp / d);
            }
        }
    }
    return rez;
}

void upd_traficker(int x, int y, int val)
{
    vector<int> a,b;
    while(x!=y)
    {
        if(lvl[x] > lvl[y])
        {
            a.push_back(x);
            x = t[x];
        }
        else
        {
            b.push_back(y);
            y = t[y];
        }
    }
    a.push_back(x);
    int nr = 0;
    int dist = a.size() + b.size();
    for(auto it : a)
    {
        update(poz[it],dist,nr,val);
        ++nr;
    }
    reverse(b.begin(),b.end());
    for(auto it : b)
    {
        update(poz[it],dist,nr,val);
        ++nr;
    }
}

int query_arb(int tp, int x, int y)
{
    if(tp<0)
    {
        return 0;
    }
    int rez = 0;
    while(l[x]!=l[y])
    {
        if(lvl[c[l[x]]] > lvl[c[l[y]]])
        {
            swap(x,y);
        }
        rez += query(tp,poz[y]) - query(tp,poz[c[l[y]]] - 1);
        y = t[c[l[y]]];
    }
    if(poz[x] > poz[y])
    {
        swap(x,y);
    }
    rez += query(tp,poz[y]) - query(tp,poz[x]-1);
    return rez;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1; i<n; i++)
    {
        int x,y;
        cin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    get_w(1);
    lvl[1] = 1;
    c[1] = 1;
    get_paths(1);
    cin>>k;
    for(int i=1; i<=k; i++)
    {
        int x,y;
        cin>>x>>y;
        upd_traficker(x,y,+1);
    }
    cin>>q;
    for(int i=1; i<=q; i++)
    {
        int tip;
        cin>>tip;
        if(tip==1)
        {
            int x,y;
            cin>>x>>y;
            upd_traficker(x,y,+1);
        }
        else if(tip==2)
        {
            int x,y;
            cin>>x>>y;
            upd_traficker(x,y,-1);
        }
        else
        {
            int x,y,t1,t2;
            cin>>x>>y>>t1>>t2;
            cout<<query_arb(t2,x,y) - query_arb(t1-1,x,y)<<'\n';
        }
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 5 ms 4436 KB Output is correct
3 Correct 6 ms 4308 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 18900 KB Output is correct
2 Correct 98 ms 16204 KB Output is correct
3 Correct 76 ms 19660 KB Output is correct
4 Correct 91 ms 19152 KB Output is correct
5 Correct 116 ms 17708 KB Output is correct
6 Correct 101 ms 18512 KB Output is correct
7 Correct 89 ms 18856 KB Output is correct
8 Correct 71 ms 20252 KB Output is correct
9 Correct 62 ms 20508 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1283 ms 50584 KB Output is correct
2 Correct 954 ms 54696 KB Output is correct
3 Correct 886 ms 55244 KB Output is correct
4 Correct 1608 ms 47468 KB Output is correct
5 Correct 1755 ms 49984 KB Output is correct
6 Correct 890 ms 54948 KB Output is correct
7 Correct 834 ms 56696 KB Output is correct
8 Correct 793 ms 56268 KB Output is correct