oj.uz

답안 #585804

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
585804 2022-06-29T11:04:54 Z Zanite Birthday gift (IZhO18_treearray) C++17
56 / 100
 4000 ms 95332 KB 
// I am now here, but I have yet to prove that I am worthy of my place here.

#include <bits/stdc++.h>
using namespace std;

using pii	= pair<int, int>;

#define fi first
#define se second

const int maxN	= 2e5 + 5;
const int logN	= 21;

int n, m, q, a[maxN];

vector<int> adj[maxN];
int tin[maxN], tout[maxN], depth[maxN];
vector<int> Euler;

struct SparseTable {
	int s;
	vector<vector<pii>> ST;

	void build() {
		s = Euler.size();

		ST.push_back(vector<pii>(0));
		for (auto i : Euler) {
			ST[0].push_back({depth[i], i});
		}

		for (int i = 1; i < logN; i++) {
			ST.push_back(vector<pii>(s));

			for (int j = 0; j <= s - (1 << i); j++) {
				ST[i][j] = min(ST[i-1][j], ST[i-1][j + (1 << (i-1))]);
			}
		}
	}

	pii query(int l, int r) {
		int d = r - l + 1;
		int t = 31 - __builtin_clz(d);

		return min(ST[t][l], ST[t][r - (1 << t) + 1]);
	}

	void print() {
		for (auto i : ST) {
			for (auto j : i) {
				printf("{%d, %d} ", j.fi, j.se);
			}
			printf("\n");
		}
	}
} TreeData;

void dfs(int cur, int par, int dpt) {
	Euler.push_back(cur);
	tin[cur] = Euler.size()-1;
	depth[cur] = dpt;

	for (auto nxt : adj[cur]) {
		if (nxt == par) continue;
		dfs(nxt, cur, dpt+1);
		Euler.push_back(cur);
	}

	tout[cur] = Euler.size()-1;
}

int LCA(int x, int y) {
	//cerr << "LCA " << x << " " << y << '\n';
	if (x == 0) return y;
	if (y == 0) return x;
	if (tin[x] > tin[y]) swap(x, y);
	return TreeData.query(tin[x], tin[y]).se;
}

bool isAncestor(int x, int y) {
	// is x an ancestor of y?
	return (LCA(x, y) == x);
}

struct Segtree {
	int sz;
	vector<int> seg;

	Segtree(int sz) : sz(sz) {
		seg.assign((sz << 2) + 1, 0);
	}

	void build(int pos, int l, int r) {
		if (l == r) {
			seg[pos] = a[l];
			return;
		}

		int m = (l + r) >> 1, lc = pos << 1, rc = lc | 1;
		build(lc, l, m);
		build(rc, m+1, r);
		seg[pos] = LCA(seg[lc], seg[rc]);
	}
	void build() {build(1, 1, sz);}

	void update(int pos, int l, int r, int idx, int val) {
		if (l == r) {
			seg[pos] = val;
			return;
		}

		int m = (l + r) >> 1, lc = pos << 1, rc = lc | 1;
		if (idx <= m) {
			update(lc, l, m, idx, val);
		} else {
			update(rc, m+1, r, idx, val);
		}
		seg[pos] = LCA(seg[lc], seg[rc]);
	}
	void update(int idx, int val) {update(1, 1, sz, idx, val);}

	int query(int pos, int l, int r, int ql, int qr) {
		if (l > qr || ql > r) return 0;
		if (ql <= l && r <= qr) return seg[pos];

		int m = (l + r) >> 1, lc = pos << 1, rc = lc | 1;
		return LCA(query(lc, l, m, ql, qr), query(rc, m+1, r, ql, qr));
	}
	int query(int ql, int qr) {return query(1, 1, sz, ql, qr);}

} S(1);

#define debug(x) //cerr << #x << " = " << (x) << '\n'

pii solve(int l, int r, int v) {
	for (int i = l; i <= r; i++) {
		debug(i); debug(a[i]);
		
		if (!isAncestor(a[i], v) && !isAncestor(v, a[i])) continue;

		int cl = i, cr = r;
		while (cl <= cr) {
			debug(cl); debug(cr);
			int cm = (cl + cr) >> 1;
			int x = S.query(i, cm);
			
			if (x == v) {
				return {i, cm};
			} else if (isAncestor(x, v)) {
				cr = cm - 1;
			} else {
				cl = cm + 1;
			}
		}
	}

	return {-1, -1};
}

int main() {
	scanf("%d %d %d", &n, &m, &q);
	for (int u, v, i = 1; i < n; i++) {
		scanf("%d %d", &u, &v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(1, 0, 0);
	TreeData.build();

	/*
	TreeData.print();
	for (int i = 1; i <= n; i++) {
		cout << tin[i] << '\n';
	}
	*/

	//printf("1 3\n3 3\n-1 -1\n");

	for (int i = 1; i <= m; i++) {
		scanf("%d", &a[i]);
	}
	S = Segtree(m);
	S.build();

	for (int typ, pos, l, r, v, i = 1; i <= q; i++) {
		scanf("%d", &typ);

		if (typ == 1) {
			scanf("%d %d", &pos, &v);
			a[pos] = v;
			S.update(pos, v);

		} else {
			scanf("%d %d %d", &l, &r, &v);
			pii ans = solve(l, r, v);
			printf("%d %d\n", ans.fi, ans.se);

		}
	}
}

Compilation message

treearray.cpp: In function 'int main()':
treearray.cpp:161:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  161 |  scanf("%d %d %d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:163:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  163 |   scanf("%d %d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~
treearray.cpp:180:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  180 |   scanf("%d", &a[i]);
      |   ~~~~~^~~~~~~~~~~~~
treearray.cpp:186:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  186 |   scanf("%d", &typ);
      |   ~~~~~^~~~~~~~~~~~
treearray.cpp:189:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  189 |    scanf("%d %d", &pos, &v);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~
treearray.cpp:194:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  194 |    scanf("%d %d %d", &l, &r, &v);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB n=5
2 Correct 2 ms 4948 KB n=100
3 Correct 3 ms 5076 KB n=100
4 Correct 3 ms 4948 KB n=100
5 Correct 3 ms 4948 KB n=100
6 Correct 4 ms 4948 KB n=100
7 Correct 4 ms 4948 KB n=100
8 Correct 3 ms 4948 KB n=100
9 Correct 3 ms 4948 KB n=100
10 Correct 4 ms 4948 KB n=100
11 Correct 4 ms 4948 KB n=100
12 Correct 3 ms 4948 KB n=100
13 Correct 3 ms 5008 KB n=100
14 Correct 4 ms 4948 KB n=100
15 Correct 3 ms 4948 KB n=100
16 Correct 3 ms 5008 KB n=100
17 Correct 3 ms 4948 KB n=100
18 Correct 3 ms 4948 KB n=100
19 Correct 2 ms 4948 KB n=100
20 Correct 3 ms 4948 KB n=100
21 Correct 4 ms 4948 KB n=100
22 Correct 3 ms 5008 KB n=100
23 Correct 5 ms 4948 KB n=100
24 Correct 4 ms 4948 KB n=100
25 Correct 3 ms 5008 KB n=100
26 Correct 3 ms 4948 KB n=12
27 Correct 3 ms 4948 KB n=100

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB n=5
2 Correct 2 ms 4948 KB n=100
3 Correct 3 ms 5076 KB n=100
4 Correct 3 ms 4948 KB n=100
5 Correct 3 ms 4948 KB n=100
6 Correct 4 ms 4948 KB n=100
7 Correct 4 ms 4948 KB n=100
8 Correct 3 ms 4948 KB n=100
9 Correct 3 ms 4948 KB n=100
10 Correct 4 ms 4948 KB n=100
11 Correct 4 ms 4948 KB n=100
12 Correct 3 ms 4948 KB n=100
13 Correct 3 ms 5008 KB n=100
14 Correct 4 ms 4948 KB n=100
15 Correct 3 ms 4948 KB n=100
16 Correct 3 ms 5008 KB n=100
17 Correct 3 ms 4948 KB n=100
18 Correct 3 ms 4948 KB n=100
19 Correct 2 ms 4948 KB n=100
20 Correct 3 ms 4948 KB n=100
21 Correct 4 ms 4948 KB n=100
22 Correct 3 ms 5008 KB n=100
23 Correct 5 ms 4948 KB n=100
24 Correct 4 ms 4948 KB n=100
25 Correct 3 ms 5008 KB n=100
26 Correct 3 ms 4948 KB n=12
27 Correct 3 ms 4948 KB n=100
28 Correct 3 ms 5204 KB n=500
29 Correct 23 ms 5260 KB n=500
30 Correct 20 ms 5224 KB n=500
31 Correct 20 ms 5204 KB n=500
32 Correct 3 ms 5204 KB n=500
33 Correct 15 ms 5204 KB n=500
34 Correct 3 ms 5228 KB n=500
35 Correct 25 ms 5204 KB n=500
36 Correct 74 ms 5204 KB n=500
37 Correct 68 ms 5236 KB n=500
38 Correct 64 ms 5204 KB n=500
39 Correct 24 ms 5204 KB n=500
40 Correct 22 ms 5204 KB n=500
41 Correct 24 ms 5148 KB n=500
42 Correct 34 ms 5164 KB n=500
43 Correct 34 ms 5228 KB n=500
44 Correct 38 ms 5124 KB n=500
45 Correct 5 ms 5204 KB n=500
46 Correct 23 ms 5144 KB n=500
47 Correct 18 ms 5204 KB n=500
48 Correct 3 ms 5204 KB n=500
49 Correct 18 ms 5216 KB n=500
50 Correct 4 ms 5144 KB n=500
51 Correct 23 ms 5204 KB n=500
52 Correct 39 ms 5240 KB n=500
53 Correct 15 ms 5144 KB n=500
54 Correct 22 ms 5256 KB n=500
55 Correct 8 ms 5140 KB n=278
56 Correct 128 ms 5236 KB n=500
57 Correct 124 ms 5148 KB n=500
58 Correct 5 ms 5204 KB n=500

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB n=5
2 Correct 2 ms 4948 KB n=100
3 Correct 3 ms 5076 KB n=100
4 Correct 3 ms 4948 KB n=100
5 Correct 3 ms 4948 KB n=100
6 Correct 4 ms 4948 KB n=100
7 Correct 4 ms 4948 KB n=100
8 Correct 3 ms 4948 KB n=100
9 Correct 3 ms 4948 KB n=100
10 Correct 4 ms 4948 KB n=100
11 Correct 4 ms 4948 KB n=100
12 Correct 3 ms 4948 KB n=100
13 Correct 3 ms 5008 KB n=100
14 Correct 4 ms 4948 KB n=100
15 Correct 3 ms 4948 KB n=100
16 Correct 3 ms 5008 KB n=100
17 Correct 3 ms 4948 KB n=100
18 Correct 3 ms 4948 KB n=100
19 Correct 2 ms 4948 KB n=100
20 Correct 3 ms 4948 KB n=100
21 Correct 4 ms 4948 KB n=100
22 Correct 3 ms 5008 KB n=100
23 Correct 5 ms 4948 KB n=100
24 Correct 4 ms 4948 KB n=100
25 Correct 3 ms 5008 KB n=100
26 Correct 3 ms 4948 KB n=12
27 Correct 3 ms 4948 KB n=100
28 Correct 3 ms 5204 KB n=500
29 Correct 23 ms 5260 KB n=500
30 Correct 20 ms 5224 KB n=500
31 Correct 20 ms 5204 KB n=500
32 Correct 3 ms 5204 KB n=500
33 Correct 15 ms 5204 KB n=500
34 Correct 3 ms 5228 KB n=500
35 Correct 25 ms 5204 KB n=500
36 Correct 74 ms 5204 KB n=500
37 Correct 68 ms 5236 KB n=500
38 Correct 64 ms 5204 KB n=500
39 Correct 24 ms 5204 KB n=500
40 Correct 22 ms 5204 KB n=500
41 Correct 24 ms 5148 KB n=500
42 Correct 34 ms 5164 KB n=500
43 Correct 34 ms 5228 KB n=500
44 Correct 38 ms 5124 KB n=500
45 Correct 5 ms 5204 KB n=500
46 Correct 23 ms 5144 KB n=500
47 Correct 18 ms 5204 KB n=500
48 Correct 3 ms 5204 KB n=500
49 Correct 18 ms 5216 KB n=500
50 Correct 4 ms 5144 KB n=500
51 Correct 23 ms 5204 KB n=500
52 Correct 39 ms 5240 KB n=500
53 Correct 15 ms 5144 KB n=500
54 Correct 22 ms 5256 KB n=500
55 Correct 8 ms 5140 KB n=278
56 Correct 128 ms 5236 KB n=500
57 Correct 124 ms 5148 KB n=500
58 Correct 5 ms 5204 KB n=500
59 Correct 6 ms 5888 KB n=2000
60 Correct 456 ms 6016 KB n=2000
61 Correct 405 ms 5972 KB n=2000
62 Correct 234 ms 5920 KB n=2000
63 Correct 5 ms 5844 KB n=2000
64 Correct 347 ms 6060 KB n=2000
65 Correct 6 ms 5916 KB n=2000
66 Correct 453 ms 6108 KB n=2000
67 Correct 9 ms 5916 KB n=2000
68 Correct 359 ms 5944 KB n=2000
69 Correct 1631 ms 6140 KB n=2000
70 Correct 1591 ms 5904 KB n=2000
71 Correct 1670 ms 5900 KB n=2000
72 Correct 533 ms 5888 KB n=2000
73 Correct 539 ms 6020 KB n=2000
74 Correct 5 ms 5844 KB n=1844
75 Correct 541 ms 6020 KB n=2000
76 Correct 811 ms 5964 KB n=2000
77 Correct 793 ms 5884 KB n=2000
78 Correct 852 ms 5892 KB n=2000
79 Correct 6 ms 5844 KB n=2000
80 Correct 390 ms 5996 KB n=2000
81 Correct 317 ms 5936 KB n=2000
82 Correct 6 ms 5844 KB n=2000
83 Correct 387 ms 5964 KB n=2000
84 Correct 13 ms 5844 KB n=2000
85 Correct 331 ms 5928 KB n=2000
86 Correct 283 ms 5844 KB n=2000
87 Correct 21 ms 5916 KB n=2000
88 Correct 3411 ms 6016 KB n=2000
89 Correct 3459 ms 6008 KB n=2000
90 Correct 499 ms 5972 KB n=2000
91 Correct 32 ms 5844 KB n=2000

Subtask #4
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB n=5
2 Correct 2 ms 4948 KB n=100
3 Correct 3 ms 5076 KB n=100
4 Correct 3 ms 4948 KB n=100
5 Correct 3 ms 4948 KB n=100
6 Correct 4 ms 4948 KB n=100
7 Correct 4 ms 4948 KB n=100
8 Correct 3 ms 4948 KB n=100
9 Correct 3 ms 4948 KB n=100
10 Correct 4 ms 4948 KB n=100
11 Correct 4 ms 4948 KB n=100
12 Correct 3 ms 4948 KB n=100
13 Correct 3 ms 5008 KB n=100
14 Correct 4 ms 4948 KB n=100
15 Correct 3 ms 4948 KB n=100
16 Correct 3 ms 5008 KB n=100
17 Correct 3 ms 4948 KB n=100
18 Correct 3 ms 4948 KB n=100
19 Correct 2 ms 4948 KB n=100
20 Correct 3 ms 4948 KB n=100
21 Correct 4 ms 4948 KB n=100
22 Correct 3 ms 5008 KB n=100
23 Correct 5 ms 4948 KB n=100
24 Correct 4 ms 4948 KB n=100
25 Correct 3 ms 5008 KB n=100
26 Correct 3 ms 4948 KB n=12
27 Correct 3 ms 4948 KB n=100
28 Correct 3 ms 5204 KB n=500
29 Correct 23 ms 5260 KB n=500
30 Correct 20 ms 5224 KB n=500
31 Correct 20 ms 5204 KB n=500
32 Correct 3 ms 5204 KB n=500
33 Correct 15 ms 5204 KB n=500
34 Correct 3 ms 5228 KB n=500
35 Correct 25 ms 5204 KB n=500
36 Correct 74 ms 5204 KB n=500
37 Correct 68 ms 5236 KB n=500
38 Correct 64 ms 5204 KB n=500
39 Correct 24 ms 5204 KB n=500
40 Correct 22 ms 5204 KB n=500
41 Correct 24 ms 5148 KB n=500
42 Correct 34 ms 5164 KB n=500
43 Correct 34 ms 5228 KB n=500
44 Correct 38 ms 5124 KB n=500
45 Correct 5 ms 5204 KB n=500
46 Correct 23 ms 5144 KB n=500
47 Correct 18 ms 5204 KB n=500
48 Correct 3 ms 5204 KB n=500
49 Correct 18 ms 5216 KB n=500
50 Correct 4 ms 5144 KB n=500
51 Correct 23 ms 5204 KB n=500
52 Correct 39 ms 5240 KB n=500
53 Correct 15 ms 5144 KB n=500
54 Correct 22 ms 5256 KB n=500
55 Correct 8 ms 5140 KB n=278
56 Correct 128 ms 5236 KB n=500
57 Correct 124 ms 5148 KB n=500
58 Correct 5 ms 5204 KB n=500
59 Correct 6 ms 5888 KB n=2000
60 Correct 456 ms 6016 KB n=2000
61 Correct 405 ms 5972 KB n=2000
62 Correct 234 ms 5920 KB n=2000
63 Correct 5 ms 5844 KB n=2000
64 Correct 347 ms 6060 KB n=2000
65 Correct 6 ms 5916 KB n=2000
66 Correct 453 ms 6108 KB n=2000
67 Correct 9 ms 5916 KB n=2000
68 Correct 359 ms 5944 KB n=2000
69 Correct 1631 ms 6140 KB n=2000
70 Correct 1591 ms 5904 KB n=2000
71 Correct 1670 ms 5900 KB n=2000
72 Correct 533 ms 5888 KB n=2000
73 Correct 539 ms 6020 KB n=2000
74 Correct 5 ms 5844 KB n=1844
75 Correct 541 ms 6020 KB n=2000
76 Correct 811 ms 5964 KB n=2000
77 Correct 793 ms 5884 KB n=2000
78 Correct 852 ms 5892 KB n=2000
79 Correct 6 ms 5844 KB n=2000
80 Correct 390 ms 5996 KB n=2000
81 Correct 317 ms 5936 KB n=2000
82 Correct 6 ms 5844 KB n=2000
83 Correct 387 ms 5964 KB n=2000
84 Correct 13 ms 5844 KB n=2000
85 Correct 331 ms 5928 KB n=2000
86 Correct 283 ms 5844 KB n=2000
87 Correct 21 ms 5916 KB n=2000
88 Correct 3411 ms 6016 KB n=2000
89 Correct 3459 ms 6008 KB n=2000
90 Correct 499 ms 5972 KB n=2000
91 Correct 32 ms 5844 KB n=2000
92 Correct 781 ms 93472 KB n=200000
93 Execution timed out 4048 ms 95332 KB Time limit exceeded
94 Halted 0 ms 0 KB -