Submission #642717

#	Time	Username	Problem	Language	Result	Execution time	Memory
642717		MadokaMagicaFan	Traffickers (RMI18_traffickers)	C++17	90 / 100	3598 ms	29140 KiB

traffickers

#include "bits/stdc++.h"

/* #define ONPC */
#define sz(v)       ((int)(v.size()))
#define pb          push_back

#pragma GCC optimize("O1")
#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
/* #pragma GCC optimize("Ofast") */
/* #pragma GCC target("avx,avx2,fma") */
/* #pragma GCC target("popcnt") */

using ll = long long;

using namespace std;

struct aib{
    vector<int> f;
    int n;
    aib (int _n) {
        f.assign(_n, 0);
        n = _n;
    }

    void add(int x, int v) {
        for (; x < n; x |= (x+1))
            f[x] += v;
    }

    int ask(int x) {
        int res = 0;
        for (; x >= 0; x = (x&(x+1)) - 1)
            res += f[x];
        return res;
    }

    int ask(int l, int r) {
        if (l > r)
            swap(l,r);
        return ask(r) - ask(l-1);
    }
};

int n;
vector<int> p;
vector<int> c;
vector<int> hv;
vector<int> head;
vector<int> d;
vector<int> in;
vector<aib> tr[20];

int icnt = 0;

int
lca(int a, int b)
{
    while (head[a] != head[b]) {
        if (d[head[a]] > d[head[b]])
            a = p[head[a]];
        else
            b = p[head[b]];
    }
    if (d[a] > d[b])
        a = b;
    return a;
}

int
dist(int a, int b)
{
    return d[a] + d[b] - 2 * d[lca(a,b)] + 1;
}

int
dfs(vector<vector<int>> &adj, int x)
{
    int cnt, mcnt = 0;
    for (int u : adj[x]) {
        if (u == p[x]) continue;
        ++c[x];

        p[u] = x;
        d[u] = d[x] + 1;
        cnt = dfs(adj,u);
        if (cnt > mcnt) {
            mcnt = cnt;
            hv[x] = u;
        }
    }

    for (int u : adj[x]) {
        if (u == p[x]) continue;

    }
    return c[x];
}

void
dfs_head(vector<vector<int>> &adj, int x, int h)
{
    head[x] = h;
    in[x] = icnt++;
    if (hv[x])
        dfs_head(adj,hv[x],h);
    for (int u : adj[x]) {
        if (u == p[x]) continue;
        ++c[x];

        if (hv[x] != u)
            dfs_head(adj,u,u);
    }
    return;
}

void
addline(int a, int b, int dif)
{
    int l = lca(a,b);
    int x, c = 0;
    int dist = d[a] + d[b] + 1 - 2 * d[l];
    x = 1;
    while (x * dist < 11)
        ++x;

    while (a != l) {
        if (dist > 1 && dist < 11) {
            for (int j = c; j < x*dist; ++j) {
                if ((j % dist) < c)
                    tr[x*dist-1][j].add(in[a], (j/dist)*dif);
                else
                    tr[x*dist-1][j].add(in[a], (j/dist + 1)*dif);
            }
        } else {
            for (int j = c; j < dist; ++j)
                tr[dist-1][j].add(in[a], dif);
        }
        ++c;
        a = p[a];
    }

    if (dist > 1 && dist < 11) {
        for (int j = c; j < x*dist; ++j) {
            if ((j % dist) < c)
                tr[x*dist-1][j].add(in[l], (j/dist)*dif);
            else
                tr[x*dist-1][j].add(in[l], (j/dist + 1)*dif);
        }
    } else {
        for (int j = c; j < dist; ++j) {
            tr[dist-1][j].add(in[l], dif);
        }
    }

    c = dist - 1;
    while (b != l) {
        if (dist > 1 && dist < 11) {
            for (int j = c; j < x*dist; ++j) {
                if ((j % dist) < c)
                    tr[x*dist-1][j].add(in[b], (j/dist)*dif);
                else
                    tr[x*dist-1][j].add(in[b], (j/dist + 1)*dif);
            }
        } else {
            for (int j = c; j < dist; ++j)
                tr[dist-1][j].add(in[b], dif);
        }
        --c;
        b = p[b];
    }
    return;
}

void
init()
{
    vector<vector<int>> adj(n);
    int a, b;
    for (int i = 0; i < n-1; ++i) {
        cin >> a >> b;
        --a,  --b;
        adj[a].pb(b);
        adj[b].pb(a);
    }

    p.assign(n,0);
    c.assign(n,0);
    d.assign(n,0);
    in.assign(n,0);
    hv.assign(n,0);
    head.assign(n,0);

    dfs(adj,0);
    dfs_head(adj,0,0);

    for (int i = 0; i < 20; ++i) {
        for (int j = 0; j < i+1; ++j) {
            tr[i].pb(aib(n));
        }
    }

    return;
}

ll
answer(int a, int b, int t, int z)
{
    static ll ans;
    static ll difs[20][3];

    ans = 0;

    for (int i = 11; i <= 20; ++i) {
        difs[i-1][0] = (t % i) - 1;
        difs[i-1][1] = (z/i) - (t/i);
        difs[i-1][2] = z % i;
    }

    difs[0][1] = z-t+1;

    /* for (int i = 2; i < 6; ++i) { */
    /*     cout << difs[i-1][0] << ' ' << difs[i-1][1] << ' ' << difs[i-1][2] << endl; */
    /* } */


    while (head[a] != head[b]) {
        if (d[head[a]] > d[head[b]]) {
            ans += difs[0][1] * ((ll)(tr[0][0].ask(in[head[a]], in[a])));
            for (int i = 11; i < 21; ++i) {
                ans += difs[i-1][1] * ((ll)(tr[i-1][i-1].ask(in[head[a]], in[a])));
                ans += ((ll)(tr[i-1][difs[i-1][2]].ask(in[head[a]], in[a])));
                if (difs[i-1][0] > -1)
                ans -= ((ll)(tr[i-1][difs[i-1][0]].ask(in[head[a]], in[a])));
            }
            a = p[head[a]];
        } else {
            ans += difs[0][1] * ((ll)(tr[0][0].ask(in[head[b]], in[b])));
            for (int i = 11; i < 21; ++i) {
                ans += difs[i-1][1] * ((ll)(tr[i-1][i-1].ask(in[head[b]], in[b])));
                ans += ((ll)(tr[i-1][difs[i-1][2]].ask(in[head[b]], in[b])));
                if (difs[i-1][0] > -1)
                ans -= ((ll)(tr[i-1][difs[i-1][0]].ask(in[head[b]], in[b])));
            }
            b = p[head[b]];
        }
    }

    ans += difs[0][1] * ((ll)(tr[0][0].ask(in[a], in[b])));
    for (int i = 11; i < 21; ++i) {
        ans += difs[i-1][1] * ((ll)(tr[i-1][i-1].ask(in[a], in[b])));
        ans += ((ll)(tr[i-1][difs[i-1][2]].ask(in[a], in[b])));
        if (difs[i-1][0] > -1)
        ans -= ((ll)(tr[i-1][difs[i-1][0]].ask(in[a], in[b])));
    }

    /* for (int i = 2; i < 21; ++i) { */
    /*     ans += an[i-1]; */
    /* } */
    /* cout << endl; */

    return ans;
}

int32_t
main(int argc, char *argv[])
{
#ifdef ONPC
    if (argc > 1)
        freopen(argv[1], "r", stdin);
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;

    init();
    int k, q, a, b;

    cin >> k;
    while (k--) {
        cin >> a >> b;
        --a, --b;
        /* assert(a!=b); */
        addline(a,b,1);
    }

    cin >> q;

    int c, t, z;

    while (q--) {
        cin >> c >>  a >> b;
        --a, --b;
        if (c < 3) {
            addline(a,b, (c == 1) ? 1 : -1);
        } else {
            cin >> t >> z;
            cout << answer(a, b, t, z) << endl;
        }
    }
    return 0;
}

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