oj.uz

Submission #878361

# Submission time Handle Problem Language Result Execution time Memory
878361 2023-11-24T08:43:03 Z TAhmed33 Tourism (JOI23_tourism) C++
0 / 100
 5000 ms 196928 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
const int MAXN = 4e5 + 25;
int in[MAXN], out[MAXN], depth[MAXN];
pair <int, int> sparse[__lg(MAXN)][MAXN];
vector <int> adj[MAXN];
int n, m, q;
int cnt = 0;
void dfs (int pos, int par, int dep = 1) {
    depth[pos] = dep;
    sparse[0][++cnt] = {dep, pos};
    in[pos] = cnt;
    for (auto j : adj[pos]) {
        if (j != par) {
            dfs(j, pos, dep + 1);
            sparse[0][++cnt] = {dep, pos};
        }
    }
    out[pos] = dep;
}
int sparse2[__lg(MAXN)][MAXN];
int query (int l, int r) {
    if (l > r) swap(l, r);
    int x = __lg(r - l + 1);
    return min(sparse[x][l], sparse[x][r - (1 << x) + 1]).second;
}
int query2 (int l, int r) {
    int x = __lg(r - l + 1);
    return query(in[sparse2[x][l]], in[sparse2[x][r - (1 << x) + 1]]);
}
int arr[MAXN];
array <int, 3> queries[MAXN];
int ret[MAXN];
int ans = 0;
set <int> dd;
void add (int x) {
    ans += depth[x];
    auto t = dd.upper_bound(in[x]);
    int r = (t == dd.end() ? -1 : *t);
    int l = (t == dd.begin() || dd.empty() ? -1 : *(--t));
    if (r != -1) ans -= depth[query(in[x], r)];
    if (l != -1) ans -= depth[query(l, in[x])];
    if (l != -1 && r != -1) ans += depth[query(l, r)];
    dd.insert(in[x]);
}
void rem (int x) {
    dd.erase(dd.lower_bound(in[x]));
    ans -= depth[x];
    auto t = dd.upper_bound(in[x]);
    int r = (t == dd.end() ? -1 : *t);
    int l = (t == dd.begin() || dd.empty() ? -1 : *(--t));
    if (r != -1) ans += depth[query(in[x], r)];
    if (l != -1) ans += depth[query(l, in[x])];
    if (l != -1 && r != -1) ans -= depth[query(l, r)];
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> q;
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(1, -1);
    for (int i = 1; i <= __lg(cnt); i++) {
        for (int j = 1; j + (1 << i) - 1 <= cnt; j++) {
            sparse[i][j] = min(sparse[i - 1][j], sparse[i - 1][j + (1 << (i - 1))]);
        }
    }
    for (int i = 1; i <= m; i++) {
        cin >> arr[i];
        sparse2[0][i] = arr[i];
    }
    for (int i = 1; i <= __lg(m); i++) {
        for (int j = 1; j + (1 << i) - 1 <= m; j++) {
            sparse2[i][j] = query(in[sparse2[i - 1][j]], in[sparse2[i - 1][j + (1 << (i - 1))]]);
        }
    }
    /*for (int i = 1; i <= q; i++) {
        int l, r;
        cin >> l >> r;
        vector <int> g;
        for (int j = l; j <= r; j++) g.push_back(arr[j]);
        sort(g.begin(), g.end(), [&] (int a, int b) {
            return in[a] < in[b];
        });
        int ans = depth[g[0]], lca = g[0];
        for (int j = 1; j < (int)g.size(); j++) {
            ans += depth[g[j]] - depth[query(in[g[j]], in[g[j - 1]])];
            lca = query(in[lca], in[g[j]]);
        }
        ans -= depth[lca]; ans++;
        cout << ans << '\n';
    }*/
    for (int i = 1; i <= q; i++) {
        cin >> queries[i][0] >> queries[i][1]; queries[i][2] = i;
    }
    int x = sqrt(m); while (x * x < m) x++; while (x * x > m) x--;
    sort(queries + 1, queries + q + 1, [&] (array <int, 3> &a, array <int, 3> &b) {
        return a[0] / x == b[0] / x ? a[1] < b[1] : a[0] / x < b[0] / x;
    });
    int l = queries[1][0], r = queries[1][1];
    for (int i = l; i <= r; i++) add(arr[i]);
    ret[queries[1][2]] = ans - depth[query2(l, r)] + 1;
    for (int i = 2; i <= q; i++) {
        int tl = queries[i][0], tr = queries[i][1];
        while (l < tl) rem(arr[l++]);
        while (l > tl) add(arr[--l]);
        while (r < tr) add(arr[++r]);
        while (r > tr) rem(arr[r--]);
        ret[queries[i][2]] = ans - depth[query2(l, r)] + 1;
    }
    for (int i = 1; i <= q; i++) cout << ret[i] << '\n';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33116 KB Output is correct
2 Runtime error 34 ms 71340 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33116 KB Output is correct
2 Runtime error 34 ms 71340 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 34 ms 71144 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 33112 KB Output is correct
2 Runtime error 118 ms 196928 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 33112 KB Output is correct
2 Execution timed out 5031 ms 35160 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33116 KB Output is correct
2 Runtime error 34 ms 71340 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -