oj.uz

Submission #878383

# Submission time Handle Problem Language Result Execution time Memory
878383 2023-11-24T09:33:37 Z TAhmed33 Tourism (JOI23_tourism) C++
0 / 100
 5000 ms 112720 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] = 1; 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] = 0; 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, 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][0], 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--]);
        memset(dd.tree, 0, sizeof(dd.tree)); ans = 0;
        for (int j = tll; j <= trr; j++) add(arr[j]); 
       /* vector <int> g;
        for (int j = tll; j <= trr; j++) g.push_back(arr[j]);
        sort(g.begin(), g.end(), [&] (int a, int b) {
            return in[a] < in[b];
        });
        ans = depth[g[0]];
        for (int j = 1; j < (int)g.size(); j++) {
            ans += depth[g[j]] - depth[query(in[g[j]], in[g[j - 1]])];
        }*/
        ret[queries[i][2]] = ans - depth[query2(tll, trr)] + 1;
	}
	for (int i = 1; i <= q; i++) cout << ret[i] << '\n';
}

Compilation message

tourism.cpp: In function 'int main()':
tourism.cpp:170:6: warning: unused variable 'l' [-Wunused-variable]
  170 |  int l = queries[1][0], r = queries[1][1];
      |      ^
tourism.cpp:170:25: warning: unused variable 'r' [-Wunused-variable]
  170 |  int l = queries[1][0], r = queries[1][1];
      |                         ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 37976 KB Output is correct
2 Correct 10 ms 40028 KB Output is correct
3 Correct 13 ms 40028 KB Output is correct
4 Correct 336 ms 56408 KB Output is correct
5 Correct 330 ms 56412 KB Output is correct
6 Correct 272 ms 56512 KB Output is correct
7 Correct 428 ms 56516 KB Output is correct
8 Correct 186 ms 58708 KB Output is correct
9 Correct 332 ms 58576 KB Output is correct
10 Correct 395 ms 58572 KB Output is correct
11 Correct 368 ms 58456 KB Output is correct
12 Correct 622 ms 58572 KB Output is correct
13 Correct 495 ms 58572 KB Output is correct
14 Correct 579 ms 58460 KB Output is correct
15 Correct 394 ms 58588 KB Output is correct
16 Correct 424 ms 58456 KB Output is correct
17 Correct 463 ms 58576 KB Output is correct
18 Correct 384 ms 58572 KB Output is correct
19 Correct 355 ms 58576 KB Output is correct
20 Correct 404 ms 58580 KB Output is correct
21 Correct 348 ms 58460 KB Output is correct
22 Correct 424 ms 58580 KB Output is correct
23 Correct 368 ms 58460 KB Output is correct
24 Correct 451 ms 58580 KB Output is correct
25 Correct 397 ms 58456 KB Output is correct
26 Correct 420 ms 58708 KB Output is correct
27 Execution timed out 5062 ms 40028 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 37976 KB Output is correct
2 Correct 10 ms 40028 KB Output is correct
3 Correct 13 ms 40028 KB Output is correct
4 Correct 336 ms 56408 KB Output is correct
5 Correct 330 ms 56412 KB Output is correct
6 Correct 272 ms 56512 KB Output is correct
7 Correct 428 ms 56516 KB Output is correct
8 Correct 186 ms 58708 KB Output is correct
9 Correct 332 ms 58576 KB Output is correct
10 Correct 395 ms 58572 KB Output is correct
11 Correct 368 ms 58456 KB Output is correct
12 Correct 622 ms 58572 KB Output is correct
13 Correct 495 ms 58572 KB Output is correct
14 Correct 579 ms 58460 KB Output is correct
15 Correct 394 ms 58588 KB Output is correct
16 Correct 424 ms 58456 KB Output is correct
17 Correct 463 ms 58576 KB Output is correct
18 Correct 384 ms 58572 KB Output is correct
19 Correct 355 ms 58576 KB Output is correct
20 Correct 404 ms 58580 KB Output is correct
21 Correct 348 ms 58460 KB Output is correct
22 Correct 424 ms 58580 KB Output is correct
23 Correct 368 ms 58460 KB Output is correct
24 Correct 451 ms 58580 KB Output is correct
25 Correct 397 ms 58456 KB Output is correct
26 Correct 420 ms 58708 KB Output is correct
27 Execution timed out 5062 ms 40028 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 40028 KB Output is correct
2 Execution timed out 5064 ms 40028 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 37976 KB Output is correct
2 Correct 2049 ms 102376 KB Output is correct
3 Correct 2472 ms 104340 KB Output is correct
4 Correct 2238 ms 106676 KB Output is correct
5 Correct 74 ms 111956 KB Output is correct
6 Correct 84 ms 111952 KB Output is correct
7 Correct 102 ms 111952 KB Output is correct
8 Correct 152 ms 111956 KB Output is correct
9 Correct 328 ms 112064 KB Output is correct
10 Correct 645 ms 112068 KB Output is correct
11 Correct 1628 ms 112076 KB Output is correct
12 Correct 3784 ms 112084 KB Output is correct
13 Execution timed out 5028 ms 112720 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 37980 KB Output is correct
2 Execution timed out 5075 ms 40028 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 37976 KB Output is correct
2 Correct 10 ms 40028 KB Output is correct
3 Correct 13 ms 40028 KB Output is correct
4 Correct 336 ms 56408 KB Output is correct
5 Correct 330 ms 56412 KB Output is correct
6 Correct 272 ms 56512 KB Output is correct
7 Correct 428 ms 56516 KB Output is correct
8 Correct 186 ms 58708 KB Output is correct
9 Correct 332 ms 58576 KB Output is correct
10 Correct 395 ms 58572 KB Output is correct
11 Correct 368 ms 58456 KB Output is correct
12 Correct 622 ms 58572 KB Output is correct
13 Correct 495 ms 58572 KB Output is correct
14 Correct 579 ms 58460 KB Output is correct
15 Correct 394 ms 58588 KB Output is correct
16 Correct 424 ms 58456 KB Output is correct
17 Correct 463 ms 58576 KB Output is correct
18 Correct 384 ms 58572 KB Output is correct
19 Correct 355 ms 58576 KB Output is correct
20 Correct 404 ms 58580 KB Output is correct
21 Correct 348 ms 58460 KB Output is correct
22 Correct 424 ms 58580 KB Output is correct
23 Correct 368 ms 58460 KB Output is correct
24 Correct 451 ms 58580 KB Output is correct
25 Correct 397 ms 58456 KB Output is correct
26 Correct 420 ms 58708 KB Output is correct
27 Execution timed out 5062 ms 40028 KB Time limit exceeded
28 Halted 0 ms 0 KB -