oj.uz

Submission #859595

# Submission time Handle Problem Language Result Execution time Memory
859595 2023-10-10T10:55:16 Z heeheeheehaaw Traffickers (RMI18_traffickers) C++17
15 / 100
 3500 ms 146004 KB 
#include <bits/stdc++.h>

using namespace std;

int n, k;
int tin[30005], tout[30005], anc[30005][23], mat[23][23], timer, cnt;
int aint[120005][23][23], heavy[30005], head[30005], pos[30005], hei[30005], siz[30005];
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 < 20; 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 < 20; 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 < 20; x++)
        {
            mat[d][x] += query(1, 1, n, pos[a], pos[b], d, x);
            int st = (t1 - (t1 % d) + x);
            if(st >= t1) st -= d;
            int dr = (t2 - (t2 % d)) + x;
            if(dr > t2) dr -= d;
            rez += ((dr - st) / d) * mat[d][x];
        }
    }

    return rez;
}

int 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 6748 KB Output is correct
2 Correct 20 ms 10844 KB Output is correct
3 Correct 25 ms 10844 KB Output is correct

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 295 ms 75100 KB Output isn't correct
2 Incorrect 360 ms 74840 KB Output isn't correct
3 Incorrect 230 ms 75604 KB Output isn't correct
4 Incorrect 291 ms 75348 KB Output isn't correct
5 Incorrect 351 ms 75356 KB Output isn't correct
6 Incorrect 310 ms 75220 KB Output isn't correct
7 Incorrect 299 ms 75100 KB Output isn't correct
8 Incorrect 255 ms 75596 KB Output isn't correct
9 Incorrect 349 ms 75536 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 3315 ms 144908 KB Output isn't correct
2 Incorrect 2828 ms 145492 KB Output isn't correct
3 Incorrect 2884 ms 145404 KB Output isn't correct
4 Execution timed out 3554 ms 143764 KB Time limit exceeded
5 Execution timed out 3532 ms 143768 KB Time limit exceeded
6 Incorrect 2763 ms 145572 KB Output isn't correct
7 Incorrect 3303 ms 146004 KB Output isn't correct
8 Incorrect 3301 ms 145204 KB Output isn't correct