Submission #985855

#	Time	Username	Problem	Language	Result	Execution time	Memory
985855		boris_mihov	Traffickers (RMI18_traffickers)	C++17	100 / 100	837 ms	36516 KiB

traffickers

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

template <class T> void chkmax(T &a, T &b) {a = std::max(a, b);};
template <class T> void chkmin(T &a, T &b) {a = std::min(a, b);};
template <class T> void chkmax(T &a, T b) {a = std::max(a, b);};
template <class T> void chkmin(T &a, T b) {a = std::min(a, b);};

typedef long long llong;
const int MAXN = 30000 + 10;
const int MAXLEN = 20 + 5;
const int MAXLOG = 16;
const int INF  = 1e9;

int n, k, q;
struct Sparse
{
    int par[MAXLOG][MAXN];
    int dep[MAXN];

    void build (int _par[], int _dep[])
    {
        for (int i = 1 ; i <= n ; ++i)
        {
            par[0][i] = _par[i];
            dep[i] = _dep[i];
        }

        for (int lg = 1 ; (1 << lg) <= n ; ++lg)
        {
            for (int i = 1 ; i <= n ; ++i)
            {   
                par[lg][i] = par[lg - 1][par[lg - 1][i]];
            }
        }
    }

    void equalize(int &u, int v)
    {
        for (int lg = MAXLOG - 1 ; lg >= 0 ; --lg)
        {
            if (dep[par[lg][u]] >= dep[v])
            {
                u = par[lg][u];
            }
        }
    }

    int calcLCA(int u, int v)
    {
        if (u == v)
        {
            return u;
        }

        for (int lg = MAXLOG - 1 ; lg >= 0 ; --lg)
        {
            if (par[lg][u] != par[lg][v])
            {
                u = par[lg][u];
                v = par[lg][v];
            }
        }

        return par[0][u];
    }

    int findLCA(int u, int v)
    {
        if (dep[u] < dep[v])
        {
            std::swap(u, v);
        }

        equalize(u, v);
        return calcLCA(u, v);
    }
};

Sparse sparse;
struct Fenwick
{
    int tree[MAXN];
    void update(int idx, int val)
    {
        for (; idx <= n ; idx += idx & (-idx))
        {
            tree[idx] += val;
        }
    }

    int query(int idx)
    {
        int res = 0;
        for (; idx > 0 ; idx -= idx & (-idx))
        {
            res += tree[idx];
        }

        return res;
    }

    void rangeUpdate(int l, int r, int val)
    {
        update(l, val);
        update(r + 1, -val);
    }
};

Fenwick cnt[MAXLEN];
Fenwick rem[MAXLEN][MAXLEN];
std::vector <int> g[MAXN];
int in[MAXN], out[MAXN], timer;
int dep[MAXN];
int par[MAXN];

void dfs(int node, int p)
{
    in[node] = ++timer;
    dep[node] = dep[p] + 1;
    par[node] = p;

    for (const int &u : g[node])
    {
        if (u == p)
        {
            continue;
        }

        dfs(u, node);
    }

    out[node] = timer;
}

void addLine(int u, int a, int b)
{
    cnt[a].rangeUpdate(in[u], out[u], 1);
    for (int i = b ; i < a ; ++i)
    {
        rem[a][i].rangeUpdate(in[u], out[u], 1);
    }
}

void remLine(int u, int a, int b)
{
    cnt[a].rangeUpdate(in[u], out[u], -1);
    for (int i = b ; i < a ; ++i)
    {
        rem[a][i].rangeUpdate(in[u], out[u], -1);
    }
}

void add(int u, int v)
{
    int lca = sparse.findLCA(u, v);
    int len = dep[u] + dep[v] - 2 * dep[lca];

    int timer = 0;
    while (true)
    {
        addLine(u, len + 1, timer);
        if (u == lca)
        {
            break;
        }

        u = par[u];
        timer++;
    }

    timer = len;
    while (v != lca)
    {
        addLine(v, len + 1, timer);
        timer--;
        v = par[v];
    }
}

void remove(int u, int v)
{
    int lca = sparse.findLCA(u, v);
    int len = dep[u] + dep[v] - 2 * dep[lca];

    int timer = 0;
    while (true)
    {
        remLine(u, len + 1, timer);
        if (u == lca)
        {
            break;
        }

        u = par[u];
        timer++;
    }

    timer = len;
    while (v != lca)
    {
        remLine(v, len + 1, timer);
        timer--;
        v = par[v];
    }
}

llong calcFor(int u, int t)
{
    llong res = 0;
    for (int len = 1 ; len <= 21 ; ++len)
    {
        res += 1LL * cnt[len].query(in[u]) * (t / len);
        res += rem[len][t % len].query(in[u]);
    }

    return res;
}

llong calcPath(int u, int v, int t)
{
    if (t < 0) return 0;
    int lca = sparse.findLCA(u, v);
    return calcFor(u, t) + calcFor(v, t) - calcFor(lca, t) - calcFor(par[lca], t);
}

llong query(int u, int v, int l, int r)
{
    return calcPath(u, v, r) - calcPath(u, v, l - 1);
}

void solve()
{
    dfs(1, 0);
    sparse.build(par, dep);

    std::cin >> k;
    for (int i = 1 ; i <= k ; ++i)
    {
        int u, v;
        std::cin >> u >> v;
        add(u, v);
    }   

    std::cin >> q;
    for (int i = 1 ; i <= q ; ++i)
    {
        int qType;
        std::cin >> qType;

        if (qType == 1)
        {
            int u, v;
            std::cin >> u >> v;
            add(u, v);
            continue;
        }

        if (qType == 2)
        {
            int u, v;
            std::cin >> u >> v;
            remove(u, v);
            continue;
        }

        int u, v, l, r;
        std::cin >> u >> v >> l >> r;
        std::cout << query(u, v, l, r) << '\n';
    }
}

void input()
{
    std::cin >> n;
    for (int i = 1 ; i < n ; ++i)
    {
        int u, v;
        std::cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 40 / 40