oj.uz

Submission #859612

# Submission time Handle Problem Language Result Execution time Memory
859612 2023-10-10T11:23:38 Z heeheeheehaaw Traffickers (RMI18_traffickers) C++17
90 / 100
 3500 ms 149348 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

int n, k;
int tin[30005], tout[30005], anc[30005][23], mat[23][23], timer, cnt;
int heavy[30005], head[30005], pos[30005], hei[30005], siz[30005];
int32_t aint[30000 * 4 + 5][23][23];
vector<int> adj[30005];

bool isanc(int u, int v)
{
    return ((tin[u] <= tin[v]) && (tout[u] >= tout[v]));
}

int lca(int u, int v)
{
    if(isanc(u, v)) return u;
    if(isanc(v, u)) return v;
    for(int i = 19; i >= 0; i--)
        if(!isanc(anc[u][i], v))
            u = anc[u][i];
    return anc[u][0];
}

void update(int nod, int st, int dr, int poz, int val, int d1, int d2)
{
    if(st == dr)
    {
        aint[nod][d1][d2] += val;
        return;
    }

    int mij = (st + dr) / 2;
    if(poz <= mij)
        update(nod * 2, st, mij, poz, val, d1, d2);
    else
        update(nod * 2 + 1, mij + 1, dr, poz, val, d1, d2);
    aint[nod][d1][d2] = aint[nod * 2][d1][d2] + aint[nod * 2 + 1][d1][d2];
}

int query(int nod, int st, int dr, int le, int ri, int d1, int d2)
{
    if(le > ri)
        return 0;
    if(le == st && ri == dr)
        return aint[nod][d1][d2];
    int mij = (st + dr) / 2;
    return query(nod * 2, st, mij, le, min(mij, ri), d1, d2) +
           query(nod * 2 + 1, mij + 1, dr, max(le, mij + 1), ri, d1, d2);
}

void dfs(int nod, int p)
{
    siz[nod] = 1;
    anc[nod][0] = p;
    for(int i = 1; i <= 19; i++)
        anc[nod][i] = anc[anc[nod][i - 1]][i - 1];
    timer++, tin[nod] = timer;

    int maxx = -1;
    for(auto it : adj[nod])
        if(it != p)
        {
            hei[it] = hei[nod] + 1;
            dfs(it, nod);
            siz[nod] += siz[it];
            if(siz[it] > maxx)
                maxx = siz[it], heavy[nod] = it;
        }

    timer++, tout[nod] = timer;
}

void decompose(int nod, int h)
{
    head[nod] = h, pos[nod] = ++cnt;
    if(heavy[nod] != -1)
        decompose(heavy[nod], h);
    for(auto it : adj[nod])
        if(anc[nod][0] != it && it != heavy[nod])
            decompose(it, it);
}

vector<int> getpath(int a, int b, int l)
{
    vector<int> ans, v2;
    while(a != l)
        ans.push_back(a), a = anc[a][0];
    ans.push_back(l);
    while(b != l)
        v2.push_back(b), b = anc[b][0];
    for(int i = (int)v2.size() - 1; i >= 0; i--)
        ans.push_back(v2[i]);
    return ans;
}

void updatepath(int a, int b, int val)
{
    int l = lca(a, b);
    vector<int> path = getpath(a, b, l);
    int d = (int)path.size();
    cnt = 0;
    for(auto it : path)
    {
        update(1, 1, n, pos[it], val, d, cnt);
        cnt++;
    }

}

int calc(int a, int b, int t1, int t2)
{
    for(int d = 1; d <= 20; d++)
        for(int x = 0; x < d; x++)
            mat[d][x] = 0;
    for(; head[a] != head[b]; b = anc[head[b]][0])
    {
        if(hei[head[a]] > hei[head[b]])
            swap(a, b);
        for(int d = 1; d <= 20; d++)
            for(int x = 0; x < d; x++)
                mat[d][x] += query(1, 1, n, pos[head[b]], pos[b], d, x);
    }

    if(hei[a] > hei[b])
        swap(a, b);
    int rez = 0;
    for(int d = 1; d <= 20; d++)
    {
        for(int x = 0; x < d; x++)
        {
            mat[d][x] += query(1, 1, n, pos[a], pos[b], d, x);
            int st = t1, dr = t2;
            if(d > 1)
            {
                while(st % d != x)
                    st++;
                while(dr >= 0 && dr % d != x)
                    dr--;
                if((dr < 0) || (st > dr))
                    continue;
            }

            rez = rez + 1LL * ((dr / d) - (st / d) + 1) * mat[d][x];
        }
    }

    return rez;
}

signed main()
{
    cin>>n;
    heavy[n] = -1;
    for(int i = 1; i < n; i++)
    {
        int a, b;
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
        heavy[i] = -1;
    }

    dfs(1, 1);
    decompose(1, 1);

    cin>>k;
    cnt = 0;
    for(int i = 1; i <= k; i++)
    {
        int a, b;
        cin>>a>>b;
        updatepath(a, b, 1);
    }

    int q;
    cin>>q;
    for(int i = 1; i <= q; i++)
    {
        int tip, a, b;
        cin>>tip>>a>>b;
        if(tip == 1)
            updatepath(a, b, 1);
        else if(tip == 2)
            updatepath(a, b, -1);
        else
        {
            int t1, t2;
            cin>>t1>>t2;
            cout<<calc(a, b, t1, t2)<<'\n';
        }
    }

    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4696 KB Output is correct
2 Correct 20 ms 10840 KB Output is correct
3 Correct 19 ms 10844 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 75280 KB Output is correct
2 Correct 307 ms 75136 KB Output is correct
3 Correct 235 ms 75600 KB Output is correct
4 Correct 268 ms 75436 KB Output is correct
5 Correct 303 ms 75472 KB Output is correct
6 Correct 279 ms 75348 KB Output is correct
7 Correct 277 ms 75344 KB Output is correct
8 Correct 245 ms 75356 KB Output is correct
9 Correct 281 ms 75604 KB Output is correct

Subtask #3
30.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2921 ms 148184 KB Output is correct
2 Correct 2612 ms 149152 KB Output is correct
3 Correct 2634 ms 148464 KB Output is correct
4 Execution timed out 3520 ms 147884 KB Time limit exceeded
5 Execution timed out 3531 ms 147428 KB Time limit exceeded
6 Correct 2637 ms 149348 KB Output is correct
7 Correct 2746 ms 149124 KB Output is correct
8 Correct 2751 ms 148920 KB Output is correct