oj.uz

답안 #878386

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
878386 2023-11-24T09:37:23 Z TAhmed33 Tourism (JOI23_tourism) C++
18 / 100
 176 ms 113464 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 insert (int x) {
        tree[x]++;
    }
    void erase (int x) {
        tree[x]--;
    }
    int left (int x) {
        for (int i = x; i >= 1; i--) if (tree[i]) return i;
        return -1;
    }
    int right (int x) {
        for (int i = x + 1; i < 2 * MAXN; i++) if (tree[i]) return i;
        return -1;
    }
    bool empty (int x) {
        bool flag = 0; for (int i = 1; i < 2 * MAXN; i++) flag |= tree[i];
        return !flag;
    }*/
    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) {
        if (x == 1) return -1;
        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++) {
		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][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
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 35164 KB Output is correct
2 Correct 7 ms 37388 KB Output is correct
3 Correct 5 ms 37400 KB Output is correct
4 Correct 13 ms 53592 KB Output is correct
5 Correct 9 ms 53596 KB Output is correct
6 Correct 10 ms 53596 KB Output is correct
7 Correct 8 ms 53596 KB Output is correct
8 Correct 8 ms 55880 KB Output is correct
9 Correct 9 ms 55644 KB Output is correct
10 Correct 10 ms 55644 KB Output is correct
11 Correct 10 ms 55888 KB Output is correct
12 Correct 9 ms 55640 KB Output is correct
13 Correct 9 ms 55640 KB Output is correct
14 Correct 8 ms 55644 KB Output is correct
15 Correct 9 ms 55848 KB Output is correct
16 Correct 9 ms 55644 KB Output is correct
17 Correct 11 ms 55880 KB Output is correct
18 Correct 11 ms 55644 KB Output is correct
19 Correct 10 ms 55824 KB Output is correct
20 Correct 9 ms 55644 KB Output is correct
21 Correct 9 ms 55644 KB Output is correct
22 Correct 9 ms 55644 KB Output is correct
23 Correct 9 ms 55728 KB Output is correct
24 Correct 9 ms 55640 KB Output is correct
25 Correct 9 ms 55644 KB Output is correct
26 Correct 9 ms 55852 KB Output is correct
27 Incorrect 6 ms 37372 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 35164 KB Output is correct
2 Correct 7 ms 37388 KB Output is correct
3 Correct 5 ms 37400 KB Output is correct
4 Correct 13 ms 53592 KB Output is correct
5 Correct 9 ms 53596 KB Output is correct
6 Correct 10 ms 53596 KB Output is correct
7 Correct 8 ms 53596 KB Output is correct
8 Correct 8 ms 55880 KB Output is correct
9 Correct 9 ms 55644 KB Output is correct
10 Correct 10 ms 55644 KB Output is correct
11 Correct 10 ms 55888 KB Output is correct
12 Correct 9 ms 55640 KB Output is correct
13 Correct 9 ms 55640 KB Output is correct
14 Correct 8 ms 55644 KB Output is correct
15 Correct 9 ms 55848 KB Output is correct
16 Correct 9 ms 55644 KB Output is correct
17 Correct 11 ms 55880 KB Output is correct
18 Correct 11 ms 55644 KB Output is correct
19 Correct 10 ms 55824 KB Output is correct
20 Correct 9 ms 55644 KB Output is correct
21 Correct 9 ms 55644 KB Output is correct
22 Correct 9 ms 55644 KB Output is correct
23 Correct 9 ms 55728 KB Output is correct
24 Correct 9 ms 55640 KB Output is correct
25 Correct 9 ms 55644 KB Output is correct
26 Correct 9 ms 55852 KB Output is correct
27 Incorrect 6 ms 37372 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 37212 KB Output is correct
2 Incorrect 6 ms 37380 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 35164 KB Output is correct
2 Correct 85 ms 99120 KB Output is correct
3 Correct 121 ms 101200 KB Output is correct
4 Correct 105 ms 105812 KB Output is correct
5 Correct 105 ms 109492 KB Output is correct
6 Correct 139 ms 109276 KB Output is correct
7 Correct 150 ms 110344 KB Output is correct
8 Correct 163 ms 110388 KB Output is correct
9 Correct 169 ms 109500 KB Output is correct
10 Correct 176 ms 109392 KB Output is correct
11 Correct 162 ms 109820 KB Output is correct
12 Correct 158 ms 109380 KB Output is correct
13 Correct 143 ms 109472 KB Output is correct
14 Correct 140 ms 111872 KB Output is correct
15 Correct 123 ms 113464 KB Output is correct
16 Correct 148 ms 110732 KB Output is correct
17 Correct 145 ms 110672 KB Output is correct
18 Correct 150 ms 110852 KB Output is correct
19 Correct 96 ms 111184 KB Output is correct
20 Correct 120 ms 111308 KB Output is correct
21 Correct 135 ms 110420 KB Output is correct
22 Correct 150 ms 110560 KB Output is correct
23 Correct 150 ms 110276 KB Output is correct
24 Correct 150 ms 111184 KB Output is correct
25 Correct 155 ms 111180 KB Output is correct
26 Correct 155 ms 110420 KB Output is correct
27 Correct 154 ms 110312 KB Output is correct
28 Correct 149 ms 110416 KB Output is correct
29 Correct 159 ms 110712 KB Output is correct
30 Correct 149 ms 110336 KB Output is correct
31 Correct 139 ms 110936 KB Output is correct
32 Correct 146 ms 111948 KB Output is correct
33 Correct 130 ms 109932 KB Output is correct
34 Correct 115 ms 111696 KB Output is correct

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 35164 KB Output is correct
2 Incorrect 6 ms 37212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 35164 KB Output is correct
2 Correct 7 ms 37388 KB Output is correct
3 Correct 5 ms 37400 KB Output is correct
4 Correct 13 ms 53592 KB Output is correct
5 Correct 9 ms 53596 KB Output is correct
6 Correct 10 ms 53596 KB Output is correct
7 Correct 8 ms 53596 KB Output is correct
8 Correct 8 ms 55880 KB Output is correct
9 Correct 9 ms 55644 KB Output is correct
10 Correct 10 ms 55644 KB Output is correct
11 Correct 10 ms 55888 KB Output is correct
12 Correct 9 ms 55640 KB Output is correct
13 Correct 9 ms 55640 KB Output is correct
14 Correct 8 ms 55644 KB Output is correct
15 Correct 9 ms 55848 KB Output is correct
16 Correct 9 ms 55644 KB Output is correct
17 Correct 11 ms 55880 KB Output is correct
18 Correct 11 ms 55644 KB Output is correct
19 Correct 10 ms 55824 KB Output is correct
20 Correct 9 ms 55644 KB Output is correct
21 Correct 9 ms 55644 KB Output is correct
22 Correct 9 ms 55644 KB Output is correct
23 Correct 9 ms 55728 KB Output is correct
24 Correct 9 ms 55640 KB Output is correct
25 Correct 9 ms 55644 KB Output is correct
26 Correct 9 ms 55852 KB Output is correct
27 Incorrect 6 ms 37372 KB Output isn't correct
28 Halted 0 ms 0 KB -