oj.uz

Submission #988818

# Submission time Handle Problem Language Result Execution time Memory
988818 2024-05-26T10:34:38 Z LOLOLO Traffickers (RMI18_traffickers) C++17
100 / 100
 1789 ms 109648 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())
 
const int N = 3e4 + 10;

struct fen{
    vector <int> f;
    int N;
    void ass(int n) {
        N = n;
        f.assign(n + 1, 0);
    }

    void upd(int i, int x) {
        for (; i <= N; i += i & (-i))
            f[i] += x;
    }

    int get(int i) {
        int s = 0;
        for (; i; i -= i & (-i))
            s += f[i];

        return s;
    }
} f[21][21];

vector <int> ed[N];
int in[N], ou[N], timer = 1, p[N][20], dep[N];
int cc[N][21][21];

void dfs(int u, int v) {
    dep[u] = dep[v] + 1;
    p[u][0] = v;
    for (int j = 1; j < 20; j++) {
        p[u][j] = p[p[u][j - 1]][j - 1];
    }

    in[u] = ++timer;
    for (auto x : ed[u]) {
        if (x == v)
            continue;

        dfs(x, u);
    }
    ou[u] = timer;
}

bool is(int a, int b) {
    return in[a] <= in[b] && ou[a] >= in[b];
}

int lca(int a, int b) {
    if (is(a, b))
        return a;

    if (is(b, a))
        return b;

    for (int j = 19; j >= 0; j--) {
        if (is(p[a][j], b) == 0)
            a = p[a][j];
    }

    return p[a][0];
}

void add(int u, int v, int c) {
    int anc = lca(u, v);
    int cnt = dep[u] + dep[v] - dep[anc] * 2 + 1;
    int x = 0, y = 1;

    while (u != p[anc][0]) {
        f[cnt][x].upd(in[u], c);
        f[cnt][x].upd(ou[u] + 1, -c);
        cc[u][cnt][x] += c;
        u = p[u][0];
        x++;
    }

    while (v != anc) {
        f[cnt][cnt - y].upd(in[v], c);
        f[cnt][cnt - y].upd(ou[v] + 1, -c);
        cc[v][cnt][cnt - y] += c;
        v = p[v][0];
        y++;
    }
}

ll answer(int u, int v, ll t) {
    if (t == -1)
        return 0;

    int anc = lca(u, v);
    ll ans = 0;
    for (int i = 1; i <= 20; i++) {
        for (int j = 0; j <= min(t, (ll)20); j++) {
            ll num = (f[i][j].get(in[u]) + f[i][j].get(in[v]) - f[i][j].get(in[anc]) * 2 + cc[anc][i][j]);
            if (num) {
                ans += (ll)((t - j) / i + 1) * num; 
            }
        }
    }

    return ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ed[0].pb(1);
    ed[1].pb(0);

    int n;
    cin >> n;

    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        ed[a].pb(b);
        ed[b].pb(a);
    }

    dfs(0, 0);

    for (int i = 1; i <= 20; i++) {
        for (int j = 0; j <= 20; j++) {
            f[i][j].ass(timer);
        }
    }

    int k;
    cin >> k;

    for (int i = 0; i < k; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b, 1);
    }

    int q;
    cin >> q;

    for (int i = 0; i < q; i++) {
        int t;
        cin >> t;
        if (t == 1) {
            int a, b;
            cin >> a >> b;
            add(a, b, 1);
        }

        if (t == 2) {
            int a, b;
            cin >> a >> b;
            add(a, b, -1);
        }

        if (t == 3) {
            int a, b, t1, t2;
            cin >> a >> b >> t1 >> t2;
            cout << answer(a, b, t2) - answer(a, b, t1 - 1) << '\n';
        }
    }

    return 0;
} 

// (n + ) * n

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1372 KB Output is correct
2 Correct 4 ms 5212 KB Output is correct
3 Correct 8 ms 4444 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 36068 KB Output is correct
2 Correct 107 ms 32492 KB Output is correct
3 Correct 98 ms 34908 KB Output is correct
4 Correct 98 ms 36264 KB Output is correct
5 Correct 102 ms 35920 KB Output is correct
6 Correct 107 ms 35960 KB Output is correct
7 Correct 94 ms 35708 KB Output is correct
8 Correct 97 ms 36528 KB Output is correct
9 Correct 92 ms 36696 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1695 ms 108920 KB Output is correct
2 Correct 1684 ms 109500 KB Output is correct
3 Correct 1626 ms 109256 KB Output is correct
4 Correct 1687 ms 108860 KB Output is correct
5 Correct 1789 ms 108352 KB Output is correct
6 Correct 1699 ms 109396 KB Output is correct
7 Correct 1157 ms 109648 KB Output is correct
8 Correct 1198 ms 109396 KB Output is correct