답안 #79487 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
79487	2018-10-14T12:18:25 Z	JustInCase	Birthday gift (IZhO18_treearray)	C++17	100 / 100	2538 ms	117124 KB

treearray

#include <bits/stdc++.h>

const int32_t MAX_N = 2e5;
const int32_t LOG_MAX_N = 18;
const int32_t MAX_M = 2e5;

class Tree {
private:
	struct Node {
		bool isVisited;
		int32_t id, inTime, outTime;
		Node *ancs[LOG_MAX_N + 5];
		std::vector< Node* > v;

		bool IsAncestorOf(Node *x) const {
			if(inTime <= x->inTime && outTime >= x->outTime) {
				return true;
			}

			return false;
		}
	};

	void DfsEuler(Node *nd, int32_t &dfsTime) {
		nd->isVisited = true;
		nd->inTime = dfsTime++;

		for(auto &x : nd->v) {
			if(x->isVisited) {
				nd->ancs[0] = x;
			}
			else {
				DfsEuler(x, dfsTime);
			}
		}

		nd->outTime = dfsTime - 1;
	}
	
public:
	int32_t cntNodes;
	Node nodes[MAX_N + 5];

	void Init(int32_t _cntNodes) {
		cntNodes = _cntNodes;

		for(int32_t i = 1; i <= _cntNodes; i++) {
			nodes[i].id = i;
			
			for(int32_t j = 0; j < LOG_MAX_N; j++) {
				nodes[i].ancs[j] = nullptr;
			}
		}
	}
	
	void AddEdge(Node *x, Node *y) {
		x->v.push_back(y);
		y->v.push_back(x);
	}

	void PrecomputeInOutTimes() {
		int32_t dfsTime = 0;
		DfsEuler(&nodes[1], dfsTime);
	}

	void PrecomputeAncs() {
		for(int32_t j = 1; j < LOG_MAX_N; j++) {
			for(int32_t i = 1; i <= cntNodes; i++) {
				if(nodes[i].ancs[j - 1] != nullptr) {
					nodes[i].ancs[j] = nodes[i].ancs[j - 1]->ancs[j - 1];
				}
			}
		}
	}

	Node* FindLca(Node *x, Node *y) {
		if(x->IsAncestorOf(y)) {
			return x;
		}
		else if(y->IsAncestorOf(x)) {
			return y;
		}

		for(int32_t j = LOG_MAX_N - 1; j >= 0; j--) {
			if(x->ancs[j] != nullptr && !x->ancs[j]->IsAncestorOf(y)) {
				x = x->ancs[j];
			}
		}

		return x->ancs[0];
	}
};

int32_t a[MAX_M + 5];
Tree t;
	
int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int32_t n, m, q;
	std::cin >> n >> m >> q;
	
	t.Init(n);
	for(int32_t i = 0; i < n - 1; i++) {
		int32_t u, v;
		std::cin >> u >> v;

		t.AddEdge(&t.nodes[u], &t.nodes[v]);
	}

	t.PrecomputeInOutTimes();
	t.PrecomputeAncs();
	
	std::set< std::pair< int32_t, int32_t > > activeLcas;
	std::set< std::pair< int32_t, int32_t > > single; 
	for(int32_t i = 0; i < m; i++) {
		std::cin >> a[i];

		if(i != 0) {
			activeLcas.insert({ t.FindLca(&t.nodes[a[i - 1]], &t.nodes[a[i]])->id, i - 1 });
		}
		single.insert({ a[i], i });
	}


	for(int32_t i = 0; i < q; i++) {
		int32_t type;
		std::cin >> type;

		if(type == 1) {
			int32_t pos, v;
			std::cin >> pos >> v;
			
			pos--;
	
			if(pos != 0) {
				activeLcas.erase({ t.FindLca(&t.nodes[a[pos - 1]], &t.nodes[a[pos]])->id, pos - 1 });
			}
			if(pos != m - 1) {
				activeLcas.erase({ t.FindLca(&t.nodes[a[pos]], &t.nodes[a[pos + 1]])->id, pos });
			}
			single.erase({ a[pos], pos });

			a[pos] = v;

			if(pos != 0) {
				activeLcas.insert({ t.FindLca(&t.nodes[a[pos - 1]], &t.nodes[a[pos]])->id, pos - 1 });
			}
			if(pos != m - 1) {
				activeLcas.insert({ t.FindLca(&t.nodes[a[pos]], &t.nodes[a[pos + 1]])->id, pos });
			}
			single.insert({ a[pos], pos });
		}
		else {
			int32_t l, r, v;
			std::cin >> l >> r >> v;

			l--;
			r--;

			auto it = activeLcas.lower_bound({ v, l });
			if(it != activeLcas.end() && it->first == v && it->second < r) {
				std::cout << it->second + 1 << " " << it->second + 2 << '\n';	
			}
			else {
				auto itSingle = single.lower_bound({ v, l });
				if(itSingle != single.end() && itSingle->first == v && itSingle->second <= r) {
					std::cout << itSingle->second + 1 << " " << itSingle->second + 1 << '\n';
				}
				else {
					std::cout << -1 << " " << -1 << '\n';
				}
			}
		}
	}
}

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	37 ms	44152 KB	n=5
2	Correct	35 ms	44152 KB	n=100
3	Correct	37 ms	44332 KB	n=100
4	Correct	35 ms	44372 KB	n=100
5	Correct	36 ms	44372 KB	n=100
6	Correct	35 ms	44372 KB	n=100
7	Correct	35 ms	44372 KB	n=100
8	Correct	37 ms	44372 KB	n=100
9	Correct	36 ms	44492 KB	n=100
10	Correct	37 ms	44492 KB	n=100
11	Correct	38 ms	44492 KB	n=100
12	Correct	36 ms	44492 KB	n=100
13	Correct	36 ms	44492 KB	n=100
14	Correct	36 ms	44492 KB	n=100
15	Correct	37 ms	44492 KB	n=100
16	Correct	44 ms	44524 KB	n=100
17	Correct	36 ms	44524 KB	n=100
18	Correct	44 ms	44524 KB	n=100
19	Correct	43 ms	44524 KB	n=100
20	Correct	35 ms	44524 KB	n=100
21	Correct	47 ms	44524 KB	n=100
22	Correct	45 ms	44524 KB	n=100
23	Correct	37 ms	44524 KB	n=100
24	Correct	40 ms	44524 KB	n=100
25	Correct	36 ms	44524 KB	n=100
26	Correct	38 ms	44524 KB	n=12
27	Correct	36 ms	44524 KB	n=100

Subtask #2
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	37 ms	44152 KB	n=5
2	Correct	35 ms	44152 KB	n=100
3	Correct	37 ms	44332 KB	n=100
4	Correct	35 ms	44372 KB	n=100
5	Correct	36 ms	44372 KB	n=100
6	Correct	35 ms	44372 KB	n=100
7	Correct	35 ms	44372 KB	n=100
8	Correct	37 ms	44372 KB	n=100
9	Correct	36 ms	44492 KB	n=100
10	Correct	37 ms	44492 KB	n=100
11	Correct	38 ms	44492 KB	n=100
12	Correct	36 ms	44492 KB	n=100
13	Correct	36 ms	44492 KB	n=100
14	Correct	36 ms	44492 KB	n=100
15	Correct	37 ms	44492 KB	n=100
16	Correct	44 ms	44524 KB	n=100
17	Correct	36 ms	44524 KB	n=100
18	Correct	44 ms	44524 KB	n=100
19	Correct	43 ms	44524 KB	n=100
20	Correct	35 ms	44524 KB	n=100
21	Correct	47 ms	44524 KB	n=100
22	Correct	45 ms	44524 KB	n=100
23	Correct	37 ms	44524 KB	n=100
24	Correct	40 ms	44524 KB	n=100
25	Correct	36 ms	44524 KB	n=100
26	Correct	38 ms	44524 KB	n=12
27	Correct	36 ms	44524 KB	n=100
28	Correct	37 ms	44524 KB	n=500
29	Correct	37 ms	44524 KB	n=500
30	Correct	37 ms	44524 KB	n=500
31	Correct	38 ms	44524 KB	n=500
32	Correct	36 ms	44524 KB	n=500
33	Correct	37 ms	44524 KB	n=500
34	Correct	36 ms	44524 KB	n=500
35	Correct	37 ms	44524 KB	n=500
36	Correct	36 ms	44528 KB	n=500
37	Correct	38 ms	44528 KB	n=500
38	Correct	38 ms	44528 KB	n=500
39	Correct	38 ms	44528 KB	n=500
40	Correct	38 ms	44528 KB	n=500
41	Correct	39 ms	44528 KB	n=500
42	Correct	38 ms	44528 KB	n=500
43	Correct	37 ms	44528 KB	n=500
44	Correct	37 ms	44528 KB	n=500
45	Correct	37 ms	44528 KB	n=500
46	Correct	37 ms	44528 KB	n=500
47	Correct	36 ms	44528 KB	n=500
48	Correct	36 ms	44528 KB	n=500
49	Correct	37 ms	44528 KB	n=500
50	Correct	39 ms	44528 KB	n=500
51	Correct	40 ms	44528 KB	n=500
52	Correct	35 ms	44528 KB	n=500
53	Correct	39 ms	44528 KB	n=500
54	Correct	36 ms	44528 KB	n=500
55	Correct	39 ms	44528 KB	n=278
56	Correct	36 ms	44528 KB	n=500
57	Correct	38 ms	44528 KB	n=500
58	Correct	36 ms	44528 KB	n=500

Subtask #3
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	37 ms	44152 KB	n=5
2	Correct	35 ms	44152 KB	n=100
3	Correct	37 ms	44332 KB	n=100
4	Correct	35 ms	44372 KB	n=100
5	Correct	36 ms	44372 KB	n=100
6	Correct	35 ms	44372 KB	n=100
7	Correct	35 ms	44372 KB	n=100
8	Correct	37 ms	44372 KB	n=100
9	Correct	36 ms	44492 KB	n=100
10	Correct	37 ms	44492 KB	n=100
11	Correct	38 ms	44492 KB	n=100
12	Correct	36 ms	44492 KB	n=100
13	Correct	36 ms	44492 KB	n=100
14	Correct	36 ms	44492 KB	n=100
15	Correct	37 ms	44492 KB	n=100
16	Correct	44 ms	44524 KB	n=100
17	Correct	36 ms	44524 KB	n=100
18	Correct	44 ms	44524 KB	n=100
19	Correct	43 ms	44524 KB	n=100
20	Correct	35 ms	44524 KB	n=100
21	Correct	47 ms	44524 KB	n=100
22	Correct	45 ms	44524 KB	n=100
23	Correct	37 ms	44524 KB	n=100
24	Correct	40 ms	44524 KB	n=100
25	Correct	36 ms	44524 KB	n=100
26	Correct	38 ms	44524 KB	n=12
27	Correct	36 ms	44524 KB	n=100
28	Correct	37 ms	44524 KB	n=500
29	Correct	37 ms	44524 KB	n=500
30	Correct	37 ms	44524 KB	n=500
31	Correct	38 ms	44524 KB	n=500
32	Correct	36 ms	44524 KB	n=500
33	Correct	37 ms	44524 KB	n=500
34	Correct	36 ms	44524 KB	n=500
35	Correct	37 ms	44524 KB	n=500
36	Correct	36 ms	44528 KB	n=500
37	Correct	38 ms	44528 KB	n=500
38	Correct	38 ms	44528 KB	n=500
39	Correct	38 ms	44528 KB	n=500
40	Correct	38 ms	44528 KB	n=500
41	Correct	39 ms	44528 KB	n=500
42	Correct	38 ms	44528 KB	n=500
43	Correct	37 ms	44528 KB	n=500
44	Correct	37 ms	44528 KB	n=500
45	Correct	37 ms	44528 KB	n=500
46	Correct	37 ms	44528 KB	n=500
47	Correct	36 ms	44528 KB	n=500
48	Correct	36 ms	44528 KB	n=500
49	Correct	37 ms	44528 KB	n=500
50	Correct	39 ms	44528 KB	n=500
51	Correct	40 ms	44528 KB	n=500
52	Correct	35 ms	44528 KB	n=500
53	Correct	39 ms	44528 KB	n=500
54	Correct	36 ms	44528 KB	n=500
55	Correct	39 ms	44528 KB	n=278
56	Correct	36 ms	44528 KB	n=500
57	Correct	38 ms	44528 KB	n=500
58	Correct	36 ms	44528 KB	n=500
59	Correct	41 ms	44728 KB	n=2000
60	Correct	42 ms	44780 KB	n=2000
61	Correct	41 ms	44796 KB	n=2000
62	Correct	41 ms	44796 KB	n=2000
63	Correct	40 ms	44796 KB	n=2000
64	Correct	42 ms	44828 KB	n=2000
65	Correct	42 ms	44828 KB	n=2000
66	Correct	40 ms	44828 KB	n=2000
67	Correct	41 ms	44952 KB	n=2000
68	Correct	42 ms	44952 KB	n=2000
69	Correct	40 ms	44952 KB	n=2000
70	Correct	42 ms	44952 KB	n=2000
71	Correct	44 ms	44952 KB	n=2000
72	Correct	39 ms	44952 KB	n=2000
73	Correct	38 ms	44952 KB	n=2000
74	Correct	40 ms	44952 KB	n=1844
75	Correct	41 ms	44952 KB	n=2000
76	Correct	43 ms	44952 KB	n=2000
77	Correct	41 ms	44952 KB	n=2000
78	Correct	41 ms	44952 KB	n=2000
79	Correct	41 ms	44952 KB	n=2000
80	Correct	41 ms	44952 KB	n=2000
81	Correct	42 ms	44952 KB	n=2000
82	Correct	39 ms	44952 KB	n=2000
83	Correct	42 ms	44952 KB	n=2000
84	Correct	42 ms	44952 KB	n=2000
85	Correct	43 ms	44952 KB	n=2000
86	Correct	41 ms	44952 KB	n=2000
87	Correct	41 ms	44952 KB	n=2000
88	Correct	39 ms	44952 KB	n=2000
89	Correct	41 ms	44952 KB	n=2000
90	Correct	53 ms	44952 KB	n=2000
91	Correct	52 ms	44952 KB	n=2000

Subtask #4
44.0 / 44.0

#	결과	실행 시간	메모리	Grader output
1	Correct	37 ms	44152 KB	n=5
2	Correct	35 ms	44152 KB	n=100
3	Correct	37 ms	44332 KB	n=100
4	Correct	35 ms	44372 KB	n=100
5	Correct	36 ms	44372 KB	n=100
6	Correct	35 ms	44372 KB	n=100
7	Correct	35 ms	44372 KB	n=100
8	Correct	37 ms	44372 KB	n=100
9	Correct	36 ms	44492 KB	n=100
10	Correct	37 ms	44492 KB	n=100
11	Correct	38 ms	44492 KB	n=100
12	Correct	36 ms	44492 KB	n=100
13	Correct	36 ms	44492 KB	n=100
14	Correct	36 ms	44492 KB	n=100
15	Correct	37 ms	44492 KB	n=100
16	Correct	44 ms	44524 KB	n=100
17	Correct	36 ms	44524 KB	n=100
18	Correct	44 ms	44524 KB	n=100
19	Correct	43 ms	44524 KB	n=100
20	Correct	35 ms	44524 KB	n=100
21	Correct	47 ms	44524 KB	n=100
22	Correct	45 ms	44524 KB	n=100
23	Correct	37 ms	44524 KB	n=100
24	Correct	40 ms	44524 KB	n=100
25	Correct	36 ms	44524 KB	n=100
26	Correct	38 ms	44524 KB	n=12
27	Correct	36 ms	44524 KB	n=100
28	Correct	37 ms	44524 KB	n=500
29	Correct	37 ms	44524 KB	n=500
30	Correct	37 ms	44524 KB	n=500
31	Correct	38 ms	44524 KB	n=500
32	Correct	36 ms	44524 KB	n=500
33	Correct	37 ms	44524 KB	n=500
34	Correct	36 ms	44524 KB	n=500
35	Correct	37 ms	44524 KB	n=500
36	Correct	36 ms	44528 KB	n=500
37	Correct	38 ms	44528 KB	n=500
38	Correct	38 ms	44528 KB	n=500
39	Correct	38 ms	44528 KB	n=500
40	Correct	38 ms	44528 KB	n=500
41	Correct	39 ms	44528 KB	n=500
42	Correct	38 ms	44528 KB	n=500
43	Correct	37 ms	44528 KB	n=500
44	Correct	37 ms	44528 KB	n=500
45	Correct	37 ms	44528 KB	n=500
46	Correct	37 ms	44528 KB	n=500
47	Correct	36 ms	44528 KB	n=500
48	Correct	36 ms	44528 KB	n=500
49	Correct	37 ms	44528 KB	n=500
50	Correct	39 ms	44528 KB	n=500
51	Correct	40 ms	44528 KB	n=500
52	Correct	35 ms	44528 KB	n=500
53	Correct	39 ms	44528 KB	n=500
54	Correct	36 ms	44528 KB	n=500
55	Correct	39 ms	44528 KB	n=278
56	Correct	36 ms	44528 KB	n=500
57	Correct	38 ms	44528 KB	n=500
58	Correct	36 ms	44528 KB	n=500
59	Correct	41 ms	44728 KB	n=2000
60	Correct	42 ms	44780 KB	n=2000
61	Correct	41 ms	44796 KB	n=2000
62	Correct	41 ms	44796 KB	n=2000
63	Correct	40 ms	44796 KB	n=2000
64	Correct	42 ms	44828 KB	n=2000
65	Correct	42 ms	44828 KB	n=2000
66	Correct	40 ms	44828 KB	n=2000
67	Correct	41 ms	44952 KB	n=2000
68	Correct	42 ms	44952 KB	n=2000
69	Correct	40 ms	44952 KB	n=2000
70	Correct	42 ms	44952 KB	n=2000
71	Correct	44 ms	44952 KB	n=2000
72	Correct	39 ms	44952 KB	n=2000
73	Correct	38 ms	44952 KB	n=2000
74	Correct	40 ms	44952 KB	n=1844
75	Correct	41 ms	44952 KB	n=2000
76	Correct	43 ms	44952 KB	n=2000
77	Correct	41 ms	44952 KB	n=2000
78	Correct	41 ms	44952 KB	n=2000
79	Correct	41 ms	44952 KB	n=2000
80	Correct	41 ms	44952 KB	n=2000
81	Correct	42 ms	44952 KB	n=2000
82	Correct	39 ms	44952 KB	n=2000
83	Correct	42 ms	44952 KB	n=2000
84	Correct	42 ms	44952 KB	n=2000
85	Correct	43 ms	44952 KB	n=2000
86	Correct	41 ms	44952 KB	n=2000
87	Correct	41 ms	44952 KB	n=2000
88	Correct	39 ms	44952 KB	n=2000
89	Correct	41 ms	44952 KB	n=2000
90	Correct	53 ms	44952 KB	n=2000
91	Correct	52 ms	44952 KB	n=2000
92	Correct	1218 ms	73332 KB	n=200000
93	Correct	2130 ms	75896 KB	n=200000
94	Correct	1623 ms	78104 KB	n=200000
95	Correct	1207 ms	78104 KB	n=200000
96	Correct	1193 ms	78104 KB	n=200000
97	Correct	2294 ms	78104 KB	n=200000
98	Correct	1222 ms	78104 KB	n=200000
99	Correct	1485 ms	78104 KB	n=200000
100	Correct	1221 ms	78104 KB	n=200000
101	Correct	1419 ms	78808 KB	n=200000
102	Correct	774 ms	78808 KB	n=200000
103	Correct	764 ms	78808 KB	n=200000
104	Correct	836 ms	78808 KB	n=200000
105	Correct	783 ms	78808 KB	n=200000
106	Correct	769 ms	78808 KB	n=200000
107	Correct	814 ms	78808 KB	n=200000
108	Correct	1286 ms	78808 KB	n=200000
109	Correct	1325 ms	78808 KB	n=200000
110	Correct	1356 ms	78808 KB	n=200000
111	Correct	1193 ms	78808 KB	n=200000
112	Correct	1648 ms	78808 KB	n=200000
113	Correct	2045 ms	78808 KB	n=200000
114	Correct	1092 ms	78808 KB	n=200000
115	Correct	2239 ms	78808 KB	n=200000
116	Correct	1313 ms	78808 KB	n=200000
117	Correct	1437 ms	78816 KB	n=200000
118	Correct	2538 ms	82804 KB	n=200000
119	Correct	1266 ms	87900 KB	n=200000
120	Correct	1374 ms	100636 KB	n=200000
121	Correct	1342 ms	107696 KB	n=200000
122	Correct	1360 ms	114896 KB	n=200000
123	Correct	835 ms	117124 KB	n=200000
124	Correct	378 ms	117124 KB	n=25264

답안 #79487

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 18.0 / 18.0

Subtask #3 26.0 / 26.0

Subtask #4 44.0 / 44.0

Subtask #1
12.0 / 12.0

Subtask #2
18.0 / 18.0

Subtask #3
26.0 / 26.0

Subtask #4
44.0 / 44.0