답안 #642673

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
642673 2022-09-20T10:47:38 Z MadokaMagicaFan Traffickers (RMI18_traffickers) C++14
0 / 100
3500 ms 29132 KB
#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;
    }

    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 = 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 {
            ans += difs[0][1] * ((ll)(tr[0][0].ask(in[head[b]], in[b])));
            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]];
        }
    }

    ans += difs[0][1] * ((ll)(tr[0][0].ask(in[a], in[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[])
{
#ifdef ONPC
    if (argc > 1)
        freopen(argv[1], "r", stdin);
#endif
    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

traffickers.cpp: In function 'll answer(int, int, int, int)':
traffickers.cpp:216:15: warning: iteration 18 invokes undefined behavior [-Waggressive-loop-optimizations]
  216 |         an[i] += difs[i-1][1] * ((ll)(tr[i-1][i-1].ask(in[a], in[b])));
      |         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
traffickers.cpp:215:23: note: within this loop
  215 |     for (int i = 2; i < 21; ++i) {
      |                     ~~^~~~
traffickers.cpp:205:23: warning: iteration 18 invokes undefined behavior [-Waggressive-loop-optimizations]
  205 |                 an[i] += difs[i-1][1] * ((ll)(tr[i-1][i-1].ask(in[head[b]], in[b])));
      |                 ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
traffickers.cpp:204:31: note: within this loop
  204 |             for (int i = 2; i < 21; ++i) {
      |                             ~~^~~~
traffickers.cpp:196:23: warning: iteration 18 invokes undefined behavior [-Waggressive-loop-optimizations]
  196 |                 an[i] += difs[i-1][1] * ((ll)(tr[i-1][i-1].ask(in[head[a]], in[a])));
      |                 ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
traffickers.cpp:195:31: note: within this loop
  195 |             for (int i = 2; i < 21; ++i) {
      |                             ~~^~~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Incorrect 3 ms 1236 KB Output isn't correct
3 Incorrect 5 ms 1108 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 272 ms 9548 KB Output isn't correct
2 Incorrect 414 ms 8532 KB Output isn't correct
3 Incorrect 56 ms 9392 KB Output isn't correct
4 Incorrect 274 ms 9732 KB Output isn't correct
5 Incorrect 396 ms 9428 KB Output isn't correct
6 Incorrect 364 ms 9556 KB Output isn't correct
7 Incorrect 325 ms 9428 KB Output isn't correct
8 Incorrect 68 ms 9684 KB Output isn't correct
9 Incorrect 41 ms 9812 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3589 ms 28040 KB Time limit exceeded
2 Execution timed out 3590 ms 28920 KB Time limit exceeded
3 Incorrect 1078 ms 28408 KB Output isn't correct
4 Execution timed out 3600 ms 27448 KB Time limit exceeded
5 Incorrect 3199 ms 27348 KB Output isn't correct
6 Incorrect 1843 ms 28848 KB Output isn't correct
7 Incorrect 434 ms 29132 KB Output isn't correct
8 Incorrect 417 ms 28620 KB Output isn't correct