답안 #696306

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
696306 2023-02-06T07:57:33 Z jhwest2 Traffickers (RMI18_traffickers) C++14
0 / 100
1085 ms 54148 KB
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 30303;
const int M = 101010;

struct SEG {
    ll tree[N];

    void update(int a, int b, ll v) {
        ++b;
        for (; a < N; a += a & -a)
            tree[a] += v;
        for (; b < N; b += b & -b)
            tree[b] -= v;
    }
    ll query(int a) {
        ll res = 0;
        for (; a; a -= a & -a)
            res += tree[a];
        return res;
    }
} t[20][20];

int n, k, q, d[N], pp[20][N], dfn[N], out[N], z;
vector<int> g[N];

void dfs(int p, int v) {
    dfn[v] = ++z;
    for (int x : g[v]) {
        if (p == x)
            continue;

        pp[0][x] = v;
        d[x] = d[v] + 1;
        dfs(v, x);
    }
    out[v] = z;
}
vector<int> path(int u, int v) {
    vector<int> U, V;
    while (d[v] > d[u]) {
        V.push_back(v);
        v = pp[0][v];
    }
    while (d[u] > d[v]) {
        U.push_back(u);
        u = pp[0][u];
    }
    while (u != v) {
        U.push_back(u);
        V.push_back(v);
        u = pp[0][u]; v = pp[0][v];
    }
    while (!V.empty()) {
        U.push_back(V.back());
        V.pop_back();
    }
    return U;
}
int lca(int u, int v) {
    if (d[u] > d[v])
        swap(u, v);
    int D = d[v] - d[u];
    for (int j = 0; j < 20; j++) {
        if (D >> j & 1)
            v = pp[j][v];
    }
    for (int j = 19; j >= 0; j--) {
        if (pp[j][u] != pp[j][v]) {
            u = pp[j][u];
            v = pp[j][v];
        }
    }
    return (u == v) ? u : pp[0][u];
}
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 1);
    for (int j = 1; j < 20; j++)
        for (int i = 1; i <= n; i++)
            pp[j][i] = pp[j - 1][pp[j - 1][i]];

    cin >> k;
    for (int i = 0; i < k; i++) {
        int u, v; cin >> u >> v;
        auto S = path(u, v);
        int sz = S.size();

        for (int i = 0; i < sz; i++) 
            t[sz - 1][i].update(dfn[S[i]], out[S[i]], 1);
    }
    cin >> q;
    for (int i = 0; i < q; i++) {
        int T; cin >> T;
        if (T == 1) {
            int u, v; cin >> u >> v;
            auto S = path(u, v);
            int sz = S.size();

            for (int i = 0; i < sz; i++)
                t[sz - 1][i].update(dfn[S[i]], out[S[i]], 1);
        }
        if (T == 2) {
            int u, v; cin >> u >> v;
            auto S = path(u, v);
            int sz = S.size();

            for (int i = 0; i < sz; i++)
                t[sz - 1][i].update(dfn[S[i]], out[S[i]], -1);
        }
        if (T == 3) {
            int u, v, t1, t2; cin >> u >> v >> t1 >> t2;
            int r = lca(r, v);

            ll ans = 0;
            vector<int> s{ u, v, r, pp[0][r] };
            for (int y : s) {
                if (y == 0)
                    continue;
                for (int i = 0; i < 20; i++) {
                    for (int j = 0; j <= i; j++) {
                        ll x = t[i][j].query(dfn[y]);
                        ans += (t2 + i + 1 - j) / (i + 1) * x;
                        ans -= (t1 + i - j) / (i + 1) * x;
                    }
                }
            }
            cout << ans << '\n';
        }
    }
}

Compilation message

traffickers.cpp: In function 'int main()':
traffickers.cpp:121:24: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
  121 |             int r = lca(r, v);
      |                     ~~~^~~~~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 6100 KB Output isn't correct
2 Incorrect 5 ms 6740 KB Output isn't correct
3 Incorrect 6 ms 6688 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 82 ms 20392 KB Output isn't correct
2 Incorrect 82 ms 19432 KB Output isn't correct
3 Incorrect 80 ms 20648 KB Output isn't correct
4 Incorrect 89 ms 20512 KB Output isn't correct
5 Incorrect 92 ms 20404 KB Output isn't correct
6 Incorrect 100 ms 20500 KB Output isn't correct
7 Incorrect 80 ms 20380 KB Output isn't correct
8 Incorrect 75 ms 20540 KB Output isn't correct
9 Incorrect 58 ms 20672 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 920 ms 53272 KB Output isn't correct
2 Incorrect 903 ms 53904 KB Output isn't correct
3 Incorrect 1004 ms 53412 KB Output isn't correct
4 Incorrect 1085 ms 52776 KB Output isn't correct
5 Incorrect 988 ms 52492 KB Output isn't correct
6 Incorrect 898 ms 53888 KB Output isn't correct
7 Incorrect 785 ms 54148 KB Output isn't correct
8 Incorrect 796 ms 53764 KB Output isn't correct