oj.uz

Submission #878388

# Submission time Handle Problem Language Result Execution time Memory
878388 2023-11-24T09:39:51 Z TAhmed33 Tourism (JOI23_tourism) C++
28 / 100
 5000 ms 111908 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
const int MAXN = 4e5 + 25;
#define mid ((l + r) >> 1)
#define tl (node + 1)
#define tr (node + 2 * (mid - l + 1))
struct SegmentTree {
    int tree[2 * MAXN];
    void add (int l, int r, int a, int node) {
        if (l == r) {
            tree[node]++; return;
        }
        if (a <= mid) add(l, mid, a, tl);
        else add(mid + 1, r, a, tr);
        tree[node] = tree[tl] + tree[tr];
    }
    void rem (int l, int r, int a, int node) {
        if (l == r) {
            tree[node]--; return;
        }
        if (a <= mid) rem(l, mid, a, tl);
        else rem(mid + 1, r, a, tr);
        tree[node] = tree[tl] + tree[tr];
    }
    int get1 (int l, int r, int a, int node) {
        if (!tree[node] || r < a) return -1;
        if (l == r) return l;
        int x = get1(l, mid, a, tl);
        if (x != -1 && x >= a) return x;
        return get1(mid + 1, r, a, tr);
    }
    int get2 (int l, int r, int a, int node) {
        if (!tree[node] || l > a) return -1;
        if (l == r) return l;
        int x = get2(mid + 1, r, a, tr);
        if (x != -1 && x <= a) return x;
        return get2(l, mid, a, tl);
    }
    void insert (int x) {
        add(1, MAXN, x, 1);
    }
    void erase (int x) {
        rem(1, MAXN, x, 1);
    }
    int left (int x) {
        return get2(1, MAXN, x, 1);
    }
    int right (int x) {
        if (x == MAXN) return -1;
        return get1(1, MAXN, x + 1, 1);
    }
    bool empty () {
        return tree[1] == 0;
    }
} dd;
int in[MAXN], depth[MAXN], revin[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; revin[cnt] = pos;
	for (auto j : adj[pos]) {
		if (j != par) {
			dfs(j, pos, dep + 1);
			sparse[0][++cnt] = {dep, pos};
		}
	}
}
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;
void add (int x) {
    ans += depth[x];
    int l = dd.left(in[x]), r = dd.right(in[x]);
	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(in[x]);
    ans -= depth[x];
    int l = dd.left(in[x]), r = dd.right(in[x]);
    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++) {
		cin >> queries[i][0] >> queries[i][1]; queries[i][2] = i;
	}
	int x = 1000;
	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][1] + 1, r = queries[1][1];
	for (int i = 1; i <= q; i++) {
		int tll = queries[i][0], trr = queries[i][1];
        while (l < tll) rem(arr[l++]);
        while (l > tll) add(arr[--l]);
        while (r < trr) add(arr[++r]);
		while (r > trr) rem(arr[r--]);
        ret[queries[i][2]] = ans - depth[query2(tll, trr)] + 1;
	}
	for (int i = 1; i <= q; i++) cout << ret[i] << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 35164 KB Output is correct
2 Correct 6 ms 37316 KB Output is correct
3 Correct 5 ms 37212 KB Output is correct
4 Correct 10 ms 53828 KB Output is correct
5 Correct 8 ms 53596 KB Output is correct
6 Correct 9 ms 53592 KB Output is correct
7 Correct 9 ms 53596 KB Output is correct
8 Correct 8 ms 55844 KB Output is correct
9 Correct 13 ms 56132 KB Output is correct
10 Correct 11 ms 55652 KB Output is correct
11 Correct 11 ms 55644 KB Output is correct
12 Correct 7 ms 55812 KB Output is correct
13 Correct 7 ms 55640 KB Output is correct
14 Correct 8 ms 55644 KB Output is correct
15 Correct 11 ms 55644 KB Output is correct
16 Correct 11 ms 55644 KB Output is correct
17 Correct 11 ms 55888 KB Output is correct
18 Correct 11 ms 55896 KB Output is correct
19 Correct 11 ms 55796 KB Output is correct
20 Correct 11 ms 55644 KB Output is correct
21 Correct 11 ms 55644 KB Output is correct
22 Correct 14 ms 55644 KB Output is correct
23 Correct 11 ms 55644 KB Output is correct
24 Correct 11 ms 55640 KB Output is correct
25 Correct 14 ms 55644 KB Output is correct
26 Correct 11 ms 55644 KB Output is correct
27 Correct 8 ms 37212 KB Output is correct
28 Correct 6 ms 43356 KB Output is correct
29 Correct 7 ms 55644 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 35164 KB Output is correct
2 Correct 6 ms 37316 KB Output is correct
3 Correct 5 ms 37212 KB Output is correct
4 Correct 10 ms 53828 KB Output is correct
5 Correct 8 ms 53596 KB Output is correct
6 Correct 9 ms 53592 KB Output is correct
7 Correct 9 ms 53596 KB Output is correct
8 Correct 8 ms 55844 KB Output is correct
9 Correct 13 ms 56132 KB Output is correct
10 Correct 11 ms 55652 KB Output is correct
11 Correct 11 ms 55644 KB Output is correct
12 Correct 7 ms 55812 KB Output is correct
13 Correct 7 ms 55640 KB Output is correct
14 Correct 8 ms 55644 KB Output is correct
15 Correct 11 ms 55644 KB Output is correct
16 Correct 11 ms 55644 KB Output is correct
17 Correct 11 ms 55888 KB Output is correct
18 Correct 11 ms 55896 KB Output is correct
19 Correct 11 ms 55796 KB Output is correct
20 Correct 11 ms 55644 KB Output is correct
21 Correct 11 ms 55644 KB Output is correct
22 Correct 14 ms 55644 KB Output is correct
23 Correct 11 ms 55644 KB Output is correct
24 Correct 11 ms 55640 KB Output is correct
25 Correct 14 ms 55644 KB Output is correct
26 Correct 11 ms 55644 KB Output is correct
27 Correct 8 ms 37212 KB Output is correct
28 Correct 6 ms 43356 KB Output is correct
29 Correct 7 ms 55644 KB Output is correct
30 Correct 108 ms 64092 KB Output is correct
31 Correct 148 ms 64088 KB Output is correct
32 Correct 164 ms 64088 KB Output is correct
33 Correct 161 ms 64092 KB Output is correct
34 Correct 194 ms 64128 KB Output is correct
35 Correct 15 ms 64088 KB Output is correct
36 Correct 14 ms 64092 KB Output is correct
37 Correct 14 ms 64092 KB Output is correct
38 Correct 166 ms 64092 KB Output is correct
39 Correct 159 ms 64176 KB Output is correct
40 Correct 159 ms 64428 KB Output is correct
41 Correct 15 ms 63988 KB Output is correct
42 Correct 15 ms 64088 KB Output is correct
43 Correct 14 ms 64196 KB Output is correct
44 Correct 164 ms 64340 KB Output is correct
45 Correct 164 ms 64088 KB Output is correct
46 Correct 165 ms 64156 KB Output is correct
47 Correct 14 ms 64088 KB Output is correct
48 Correct 14 ms 64092 KB Output is correct
49 Correct 14 ms 64092 KB Output is correct
50 Correct 176 ms 64340 KB Output is correct
51 Correct 159 ms 64092 KB Output is correct
52 Correct 153 ms 64088 KB Output is correct
53 Correct 164 ms 64340 KB Output is correct
54 Correct 168 ms 64092 KB Output is correct
55 Correct 161 ms 64088 KB Output is correct
56 Correct 94 ms 41304 KB Output is correct
57 Correct 7 ms 47708 KB Output is correct
58 Correct 11 ms 64160 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 37208 KB Output is correct
2 Correct 9 ms 37208 KB Output is correct
3 Correct 96 ms 41492 KB Output is correct
4 Execution timed out 5046 ms 102480 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 35164 KB Output is correct
2 Correct 90 ms 99120 KB Output is correct
3 Correct 123 ms 101388 KB Output is correct
4 Correct 102 ms 105820 KB Output is correct
5 Correct 104 ms 109500 KB Output is correct
6 Correct 156 ms 109468 KB Output is correct
7 Correct 152 ms 110328 KB Output is correct
8 Correct 158 ms 110160 KB Output is correct
9 Correct 167 ms 109652 KB Output is correct
10 Correct 155 ms 109396 KB Output is correct
11 Correct 154 ms 109504 KB Output is correct
12 Correct 149 ms 109392 KB Output is correct
13 Correct 149 ms 109532 KB Output is correct
14 Correct 130 ms 110424 KB Output is correct
15 Correct 118 ms 111908 KB Output is correct
16 Correct 143 ms 109568 KB Output is correct
17 Correct 146 ms 109512 KB Output is correct
18 Correct 145 ms 109508 KB Output is correct
19 Correct 100 ms 110340 KB Output is correct
20 Correct 120 ms 110332 KB Output is correct
21 Correct 135 ms 109352 KB Output is correct
22 Correct 141 ms 109240 KB Output is correct
23 Correct 143 ms 109248 KB Output is correct
24 Correct 166 ms 110324 KB Output is correct
25 Correct 159 ms 110160 KB Output is correct
26 Correct 151 ms 109464 KB Output is correct
27 Correct 159 ms 109448 KB Output is correct
28 Correct 153 ms 109436 KB Output is correct
29 Correct 147 ms 109444 KB Output is correct
30 Correct 141 ms 109392 KB Output is correct
31 Correct 165 ms 109320 KB Output is correct
32 Correct 127 ms 110420 KB Output is correct
33 Correct 123 ms 109796 KB Output is correct
34 Correct 136 ms 111640 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 35164 KB Output is correct
2 Correct 10 ms 37212 KB Output is correct
3 Correct 92 ms 41400 KB Output is correct
4 Execution timed out 5053 ms 102904 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 35164 KB Output is correct
2 Correct 6 ms 37316 KB Output is correct
3 Correct 5 ms 37212 KB Output is correct
4 Correct 10 ms 53828 KB Output is correct
5 Correct 8 ms 53596 KB Output is correct
6 Correct 9 ms 53592 KB Output is correct
7 Correct 9 ms 53596 KB Output is correct
8 Correct 8 ms 55844 KB Output is correct
9 Correct 13 ms 56132 KB Output is correct
10 Correct 11 ms 55652 KB Output is correct
11 Correct 11 ms 55644 KB Output is correct
12 Correct 7 ms 55812 KB Output is correct
13 Correct 7 ms 55640 KB Output is correct
14 Correct 8 ms 55644 KB Output is correct
15 Correct 11 ms 55644 KB Output is correct
16 Correct 11 ms 55644 KB Output is correct
17 Correct 11 ms 55888 KB Output is correct
18 Correct 11 ms 55896 KB Output is correct
19 Correct 11 ms 55796 KB Output is correct
20 Correct 11 ms 55644 KB Output is correct
21 Correct 11 ms 55644 KB Output is correct
22 Correct 14 ms 55644 KB Output is correct
23 Correct 11 ms 55644 KB Output is correct
24 Correct 11 ms 55640 KB Output is correct
25 Correct 14 ms 55644 KB Output is correct
26 Correct 11 ms 55644 KB Output is correct
27 Correct 8 ms 37212 KB Output is correct
28 Correct 6 ms 43356 KB Output is correct
29 Correct 7 ms 55644 KB Output is correct
30 Correct 108 ms 64092 KB Output is correct
31 Correct 148 ms 64088 KB Output is correct
32 Correct 164 ms 64088 KB Output is correct
33 Correct 161 ms 64092 KB Output is correct
34 Correct 194 ms 64128 KB Output is correct
35 Correct 15 ms 64088 KB Output is correct
36 Correct 14 ms 64092 KB Output is correct
37 Correct 14 ms 64092 KB Output is correct
38 Correct 166 ms 64092 KB Output is correct
39 Correct 159 ms 64176 KB Output is correct
40 Correct 159 ms 64428 KB Output is correct
41 Correct 15 ms 63988 KB Output is correct
42 Correct 15 ms 64088 KB Output is correct
43 Correct 14 ms 64196 KB Output is correct
44 Correct 164 ms 64340 KB Output is correct
45 Correct 164 ms 64088 KB Output is correct
46 Correct 165 ms 64156 KB Output is correct
47 Correct 14 ms 64088 KB Output is correct
48 Correct 14 ms 64092 KB Output is correct
49 Correct 14 ms 64092 KB Output is correct
50 Correct 176 ms 64340 KB Output is correct
51 Correct 159 ms 64092 KB Output is correct
52 Correct 153 ms 64088 KB Output is correct
53 Correct 164 ms 64340 KB Output is correct
54 Correct 168 ms 64092 KB Output is correct
55 Correct 161 ms 64088 KB Output is correct
56 Correct 94 ms 41304 KB Output is correct
57 Correct 7 ms 47708 KB Output is correct
58 Correct 11 ms 64160 KB Output is correct
59 Correct 5 ms 37208 KB Output is correct
60 Correct 9 ms 37208 KB Output is correct
61 Correct 96 ms 41492 KB Output is correct
62 Execution timed out 5046 ms 102480 KB Time limit exceeded
63 Halted 0 ms 0 KB -