oj.uz

Submission #642005

# Submission time Handle Problem Language Result Execution time Memory
642005 2022-09-18T09:02:57 Z Tenis0206 Traffickers (RMI18_traffickers) C++11
80 / 100
 3500 ms 59152 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)
{
    for(int i=poz; i<=n; i+=ub(i))
    {
        aib[d][r][i] += val;
    }
}

int query(int tp, int poz)
{
    int rez = 0;
    for(int i=poz; i>=1; i-=ub(i))
    {
        for(int d=1; d<=20; d++)
        {
            for(int r=0; r<=d; r++)
            {
                if(tp >= r)
                {
                    rez += 1LL * aib[d][r][i] * ((tp - r) / d + 1);
                }
            }
        }
    }
    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 8 ms 4476 KB Output is correct
3 Correct 12 ms 4308 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 18848 KB Output is correct
2 Correct 528 ms 15920 KB Output is correct
3 Correct 245 ms 20084 KB Output is correct
4 Correct 394 ms 18940 KB Output is correct
5 Correct 493 ms 17204 KB Output is correct
6 Correct 420 ms 18256 KB Output is correct
7 Correct 397 ms 18928 KB Output is correct
8 Correct 281 ms 20576 KB Output is correct
9 Correct 321 ms 20852 KB Output is correct

Subtask #3
20.0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3551 ms 51380 KB Time limit exceeded
2 Correct 3287 ms 56448 KB Output is correct
3 Correct 3236 ms 57564 KB Output is correct
4 Execution timed out 3563 ms 46504 KB Time limit exceeded
5 Execution timed out 3556 ms 48880 KB Time limit exceeded
6 Correct 3160 ms 56672 KB Output is correct
7 Execution timed out 3559 ms 59152 KB Time limit exceeded
8 Correct 3345 ms 58680 KB Output is correct