Submission #642670

#	Time	Username	Problem	Language	Result	Execution time	Memory
642670		MadokaMagicaFan	Traffickers (RMI18_traffickers)	C++14	0 / 100	64 ms	57956 KiB

traffickers

#include "bits/stdc++.h"

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

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 c = 0;
    int dist = d[a] + d[b] + 1 - 2 * d[l];

    while (a != l) {
        for (int j = c; j < dist; ++j)
            tr[dist-1][j].add(in[a], dif);
        ++c;
        a = p[a];
    }

    for (int j = c; j < dist; ++j) {
        tr[dist-1][j].add(in[l], dif);
    }

    c = dist - 1;
    while (b != l) {
        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 an[20];
    static ll difs[20][3];

    ans = 0;

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

    /* 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]]) {
            for (int i = 2; i < 21; ++i) {
                an[i] += difs[i-1][1] * ((ll)(tr[i-1][i-1].ask(in[head[a]], in[a])));
                an[i] += ((ll)(tr[i-1][difs[i-1][2]].ask(in[head[a]], in[a])));
                if (difs[i-1][0] > -1)
                an[i] -= ((ll)(tr[i-1][difs[i-1][0]].ask(in[head[a]], in[a])));
            }
            a = p[head[a]];
        } else {
            for (int i = 2; i < 21; ++i) {
                an[i] += difs[i-1][1] * ((ll)(tr[i-1][i-1].ask(in[head[b]], in[b])));
                an[i] += ((ll)(tr[i-1][difs[i-1][2]].ask(in[head[b]], in[b])));
                if (difs[i-1][0] > -1)
                an[i] -= ((ll)(tr[i-1][difs[i-1][0]].ask(in[head[b]], in[b])));
            }
            b = p[head[b]];
        }
    }
    for (int i = 2; i < 21; ++i) {
        an[i] += difs[i-1][1] * ((ll)(tr[i-1][i-1].ask(in[a], in[b])));
        an[i] += ((ll)(tr[i-1][difs[i-1][2]].ask(in[a], in[b])));
        if (difs[i-1][0] > -1)
        an[i] -= ((ll)(tr[i-1][difs[i-1][0]].ask(in[a], in[b])));
    }

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

    return ans;
}

int32_t
main(int argc, char *argv[])
{
    if (argc > 1)
        freopen(argv[1], "r", stdin);
    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;
}

Compilation message (stderr)

traffickers.cpp: In function 'int32_t main(int, char**)':
traffickers.cpp:229:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  229 |         freopen(argv[1], "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
traffickers.cpp: In function 'll answer(int, int, int, int)':
traffickers.cpp:210:15: warning: iteration 18 invokes undefined behavior [-Waggressive-loop-optimizations]
  210 |         an[i] += difs[i-1][1] * ((ll)(tr[i-1][i-1].ask(in[a], in[b])));
      |         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
traffickers.cpp:209:23: note: within this loop
  209 |     for (int i = 2; i < 21; ++i) {
      |                     ~~^~~~
traffickers.cpp:201:23: warning: iteration 18 invokes undefined behavior [-Waggressive-loop-optimizations]
  201 |                 an[i] += difs[i-1][1] * ((ll)(tr[i-1][i-1].ask(in[head[b]], in[b])));
      |                 ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
traffickers.cpp:200:31: note: within this loop
  200 |             for (int i = 2; i < 21; ++i) {
      |                             ~~^~~~
traffickers.cpp:193:23: warning: iteration 18 invokes undefined behavior [-Waggressive-loop-optimizations]
  193 |                 an[i] += difs[i-1][1] * ((ll)(tr[i-1][i-1].ask(in[head[a]], in[a])));
      |                 ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
traffickers.cpp:192:31: note: within this loop
  192 |             for (int i = 2; i < 21; ++i) {
      |                             ~~^~~~

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