답안 #79486 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
79486	2018-10-14T12:16:45 Z	JustInCase	Birthday gift (IZhO18_treearray)	C++17	56 / 100	2286 ms	263168 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	44280 KB	n=5
2	Correct	37 ms	44540 KB	n=100
3	Correct	38 ms	44540 KB	n=100
4	Correct	36 ms	44540 KB	n=100
5	Correct	43 ms	44644 KB	n=100
6	Correct	36 ms	44664 KB	n=100
7	Correct	36 ms	44664 KB	n=100
8	Correct	36 ms	44664 KB	n=100
9	Correct	36 ms	44664 KB	n=100
10	Correct	38 ms	44664 KB	n=100
11	Correct	37 ms	44664 KB	n=100
12	Correct	42 ms	44664 KB	n=100
13	Correct	36 ms	44748 KB	n=100
14	Correct	37 ms	44748 KB	n=100
15	Correct	38 ms	44748 KB	n=100
16	Correct	37 ms	44748 KB	n=100
17	Correct	36 ms	44748 KB	n=100
18	Correct	37 ms	44748 KB	n=100
19	Correct	38 ms	44748 KB	n=100
20	Correct	35 ms	44820 KB	n=100
21	Correct	37 ms	44820 KB	n=100
22	Correct	36 ms	44820 KB	n=100
23	Correct	37 ms	44820 KB	n=100
24	Correct	46 ms	44820 KB	n=100
25	Correct	47 ms	44820 KB	n=100
26	Correct	39 ms	44820 KB	n=12
27	Correct	39 ms	44820 KB	n=100

Subtask #2
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	37 ms	44280 KB	n=5
2	Correct	37 ms	44540 KB	n=100
3	Correct	38 ms	44540 KB	n=100
4	Correct	36 ms	44540 KB	n=100
5	Correct	43 ms	44644 KB	n=100
6	Correct	36 ms	44664 KB	n=100
7	Correct	36 ms	44664 KB	n=100
8	Correct	36 ms	44664 KB	n=100
9	Correct	36 ms	44664 KB	n=100
10	Correct	38 ms	44664 KB	n=100
11	Correct	37 ms	44664 KB	n=100
12	Correct	42 ms	44664 KB	n=100
13	Correct	36 ms	44748 KB	n=100
14	Correct	37 ms	44748 KB	n=100
15	Correct	38 ms	44748 KB	n=100
16	Correct	37 ms	44748 KB	n=100
17	Correct	36 ms	44748 KB	n=100
18	Correct	37 ms	44748 KB	n=100
19	Correct	38 ms	44748 KB	n=100
20	Correct	35 ms	44820 KB	n=100
21	Correct	37 ms	44820 KB	n=100
22	Correct	36 ms	44820 KB	n=100
23	Correct	37 ms	44820 KB	n=100
24	Correct	46 ms	44820 KB	n=100
25	Correct	47 ms	44820 KB	n=100
26	Correct	39 ms	44820 KB	n=12
27	Correct	39 ms	44820 KB	n=100
28	Correct	46 ms	44852 KB	n=500
29	Correct	45 ms	44852 KB	n=500
30	Correct	39 ms	44920 KB	n=500
31	Correct	37 ms	44956 KB	n=500
32	Correct	37 ms	44956 KB	n=500
33	Correct	35 ms	44972 KB	n=500
34	Correct	45 ms	45004 KB	n=500
35	Correct	37 ms	45016 KB	n=500
36	Correct	37 ms	45032 KB	n=500
37	Correct	37 ms	45072 KB	n=500
38	Correct	37 ms	45072 KB	n=500
39	Correct	40 ms	45072 KB	n=500
40	Correct	41 ms	45084 KB	n=500
41	Correct	37 ms	45104 KB	n=500
42	Correct	38 ms	45116 KB	n=500
43	Correct	37 ms	45116 KB	n=500
44	Correct	38 ms	45144 KB	n=500
45	Correct	38 ms	45156 KB	n=500
46	Correct	38 ms	45164 KB	n=500
47	Correct	38 ms	45188 KB	n=500
48	Correct	38 ms	45196 KB	n=500
49	Correct	36 ms	45208 KB	n=500
50	Correct	37 ms	45224 KB	n=500
51	Correct	43 ms	45236 KB	n=500
52	Correct	37 ms	45252 KB	n=500
53	Correct	39 ms	45304 KB	n=500
54	Correct	37 ms	45304 KB	n=500
55	Correct	38 ms	45304 KB	n=278
56	Correct	37 ms	45304 KB	n=500
57	Correct	40 ms	45316 KB	n=500
58	Correct	37 ms	45456 KB	n=500

Subtask #3
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	37 ms	44280 KB	n=5
2	Correct	37 ms	44540 KB	n=100
3	Correct	38 ms	44540 KB	n=100
4	Correct	36 ms	44540 KB	n=100
5	Correct	43 ms	44644 KB	n=100
6	Correct	36 ms	44664 KB	n=100
7	Correct	36 ms	44664 KB	n=100
8	Correct	36 ms	44664 KB	n=100
9	Correct	36 ms	44664 KB	n=100
10	Correct	38 ms	44664 KB	n=100
11	Correct	37 ms	44664 KB	n=100
12	Correct	42 ms	44664 KB	n=100
13	Correct	36 ms	44748 KB	n=100
14	Correct	37 ms	44748 KB	n=100
15	Correct	38 ms	44748 KB	n=100
16	Correct	37 ms	44748 KB	n=100
17	Correct	36 ms	44748 KB	n=100
18	Correct	37 ms	44748 KB	n=100
19	Correct	38 ms	44748 KB	n=100
20	Correct	35 ms	44820 KB	n=100
21	Correct	37 ms	44820 KB	n=100
22	Correct	36 ms	44820 KB	n=100
23	Correct	37 ms	44820 KB	n=100
24	Correct	46 ms	44820 KB	n=100
25	Correct	47 ms	44820 KB	n=100
26	Correct	39 ms	44820 KB	n=12
27	Correct	39 ms	44820 KB	n=100
28	Correct	46 ms	44852 KB	n=500
29	Correct	45 ms	44852 KB	n=500
30	Correct	39 ms	44920 KB	n=500
31	Correct	37 ms	44956 KB	n=500
32	Correct	37 ms	44956 KB	n=500
33	Correct	35 ms	44972 KB	n=500
34	Correct	45 ms	45004 KB	n=500
35	Correct	37 ms	45016 KB	n=500
36	Correct	37 ms	45032 KB	n=500
37	Correct	37 ms	45072 KB	n=500
38	Correct	37 ms	45072 KB	n=500
39	Correct	40 ms	45072 KB	n=500
40	Correct	41 ms	45084 KB	n=500
41	Correct	37 ms	45104 KB	n=500
42	Correct	38 ms	45116 KB	n=500
43	Correct	37 ms	45116 KB	n=500
44	Correct	38 ms	45144 KB	n=500
45	Correct	38 ms	45156 KB	n=500
46	Correct	38 ms	45164 KB	n=500
47	Correct	38 ms	45188 KB	n=500
48	Correct	38 ms	45196 KB	n=500
49	Correct	36 ms	45208 KB	n=500
50	Correct	37 ms	45224 KB	n=500
51	Correct	43 ms	45236 KB	n=500
52	Correct	37 ms	45252 KB	n=500
53	Correct	39 ms	45304 KB	n=500
54	Correct	37 ms	45304 KB	n=500
55	Correct	38 ms	45304 KB	n=278
56	Correct	37 ms	45304 KB	n=500
57	Correct	40 ms	45316 KB	n=500
58	Correct	37 ms	45456 KB	n=500
59	Correct	41 ms	45604 KB	n=2000
60	Correct	41 ms	45656 KB	n=2000
61	Correct	43 ms	45700 KB	n=2000
62	Correct	40 ms	45768 KB	n=2000
63	Correct	44 ms	45824 KB	n=2000
64	Correct	47 ms	46004 KB	n=2000
65	Correct	39 ms	46004 KB	n=2000
66	Correct	64 ms	46004 KB	n=2000
67	Correct	40 ms	46024 KB	n=2000
68	Correct	47 ms	46096 KB	n=2000
69	Correct	42 ms	46176 KB	n=2000
70	Correct	39 ms	46312 KB	n=2000
71	Correct	40 ms	46312 KB	n=2000
72	Correct	51 ms	46400 KB	n=2000
73	Correct	45 ms	46400 KB	n=2000
74	Correct	42 ms	46424 KB	n=1844
75	Correct	48 ms	46424 KB	n=2000
76	Correct	49 ms	46524 KB	n=2000
77	Correct	41 ms	46576 KB	n=2000
78	Correct	40 ms	46756 KB	n=2000
79	Correct	40 ms	46756 KB	n=2000
80	Correct	43 ms	46756 KB	n=2000
81	Correct	47 ms	46832 KB	n=2000
82	Correct	47 ms	46840 KB	n=2000
83	Correct	41 ms	46888 KB	n=2000
84	Correct	40 ms	46944 KB	n=2000
85	Correct	43 ms	46960 KB	n=2000
86	Correct	42 ms	47052 KB	n=2000
87	Correct	47 ms	47112 KB	n=2000
88	Correct	42 ms	47160 KB	n=2000
89	Correct	42 ms	47216 KB	n=2000
90	Correct	42 ms	47320 KB	n=2000
91	Correct	45 ms	47416 KB	n=2000

Subtask #4
0 / 44.0

#	결과	실행 시간	메모리	Grader output
1	Correct	37 ms	44280 KB	n=5
2	Correct	37 ms	44540 KB	n=100
3	Correct	38 ms	44540 KB	n=100
4	Correct	36 ms	44540 KB	n=100
5	Correct	43 ms	44644 KB	n=100
6	Correct	36 ms	44664 KB	n=100
7	Correct	36 ms	44664 KB	n=100
8	Correct	36 ms	44664 KB	n=100
9	Correct	36 ms	44664 KB	n=100
10	Correct	38 ms	44664 KB	n=100
11	Correct	37 ms	44664 KB	n=100
12	Correct	42 ms	44664 KB	n=100
13	Correct	36 ms	44748 KB	n=100
14	Correct	37 ms	44748 KB	n=100
15	Correct	38 ms	44748 KB	n=100
16	Correct	37 ms	44748 KB	n=100
17	Correct	36 ms	44748 KB	n=100
18	Correct	37 ms	44748 KB	n=100
19	Correct	38 ms	44748 KB	n=100
20	Correct	35 ms	44820 KB	n=100
21	Correct	37 ms	44820 KB	n=100
22	Correct	36 ms	44820 KB	n=100
23	Correct	37 ms	44820 KB	n=100
24	Correct	46 ms	44820 KB	n=100
25	Correct	47 ms	44820 KB	n=100
26	Correct	39 ms	44820 KB	n=12
27	Correct	39 ms	44820 KB	n=100
28	Correct	46 ms	44852 KB	n=500
29	Correct	45 ms	44852 KB	n=500
30	Correct	39 ms	44920 KB	n=500
31	Correct	37 ms	44956 KB	n=500
32	Correct	37 ms	44956 KB	n=500
33	Correct	35 ms	44972 KB	n=500
34	Correct	45 ms	45004 KB	n=500
35	Correct	37 ms	45016 KB	n=500
36	Correct	37 ms	45032 KB	n=500
37	Correct	37 ms	45072 KB	n=500
38	Correct	37 ms	45072 KB	n=500
39	Correct	40 ms	45072 KB	n=500
40	Correct	41 ms	45084 KB	n=500
41	Correct	37 ms	45104 KB	n=500
42	Correct	38 ms	45116 KB	n=500
43	Correct	37 ms	45116 KB	n=500
44	Correct	38 ms	45144 KB	n=500
45	Correct	38 ms	45156 KB	n=500
46	Correct	38 ms	45164 KB	n=500
47	Correct	38 ms	45188 KB	n=500
48	Correct	38 ms	45196 KB	n=500
49	Correct	36 ms	45208 KB	n=500
50	Correct	37 ms	45224 KB	n=500
51	Correct	43 ms	45236 KB	n=500
52	Correct	37 ms	45252 KB	n=500
53	Correct	39 ms	45304 KB	n=500
54	Correct	37 ms	45304 KB	n=500
55	Correct	38 ms	45304 KB	n=278
56	Correct	37 ms	45304 KB	n=500
57	Correct	40 ms	45316 KB	n=500
58	Correct	37 ms	45456 KB	n=500
59	Correct	41 ms	45604 KB	n=2000
60	Correct	41 ms	45656 KB	n=2000
61	Correct	43 ms	45700 KB	n=2000
62	Correct	40 ms	45768 KB	n=2000
63	Correct	44 ms	45824 KB	n=2000
64	Correct	47 ms	46004 KB	n=2000
65	Correct	39 ms	46004 KB	n=2000
66	Correct	64 ms	46004 KB	n=2000
67	Correct	40 ms	46024 KB	n=2000
68	Correct	47 ms	46096 KB	n=2000
69	Correct	42 ms	46176 KB	n=2000
70	Correct	39 ms	46312 KB	n=2000
71	Correct	40 ms	46312 KB	n=2000
72	Correct	51 ms	46400 KB	n=2000
73	Correct	45 ms	46400 KB	n=2000
74	Correct	42 ms	46424 KB	n=1844
75	Correct	48 ms	46424 KB	n=2000
76	Correct	49 ms	46524 KB	n=2000
77	Correct	41 ms	46576 KB	n=2000
78	Correct	40 ms	46756 KB	n=2000
79	Correct	40 ms	46756 KB	n=2000
80	Correct	43 ms	46756 KB	n=2000
81	Correct	47 ms	46832 KB	n=2000
82	Correct	47 ms	46840 KB	n=2000
83	Correct	41 ms	46888 KB	n=2000
84	Correct	40 ms	46944 KB	n=2000
85	Correct	43 ms	46960 KB	n=2000
86	Correct	42 ms	47052 KB	n=2000
87	Correct	47 ms	47112 KB	n=2000
88	Correct	42 ms	47160 KB	n=2000
89	Correct	42 ms	47216 KB	n=2000
90	Correct	42 ms	47320 KB	n=2000
91	Correct	45 ms	47416 KB	n=2000
92	Correct	1244 ms	82328 KB	n=200000
93	Correct	2109 ms	92660 KB	n=200000
94	Correct	1624 ms	102484 KB	n=200000
95	Correct	1294 ms	104124 KB	n=200000
96	Correct	1320 ms	110308 KB	n=200000
97	Correct	2197 ms	120348 KB	n=200000
98	Correct	1176 ms	124592 KB	n=200000
99	Correct	1482 ms	131476 KB	n=200000
100	Correct	1252 ms	138324 KB	n=200000
101	Correct	1438 ms	151656 KB	n=200000
102	Correct	740 ms	153732 KB	n=200000
103	Correct	782 ms	160268 KB	n=200000
104	Correct	751 ms	167076 KB	n=200000
105	Correct	760 ms	174204 KB	n=200000
106	Correct	758 ms	181656 KB	n=200000
107	Correct	779 ms	188996 KB	n=200000
108	Correct	1315 ms	195000 KB	n=200000
109	Correct	1235 ms	201760 KB	n=200000
110	Correct	1251 ms	208580 KB	n=200000
111	Correct	1261 ms	214752 KB	n=200000
112	Correct	1555 ms	227540 KB	n=200000
113	Correct	2136 ms	232328 KB	n=200000
114	Correct	1183 ms	236084 KB	n=200000
115	Correct	2286 ms	244692 KB	n=200000
116	Correct	1230 ms	250492 KB	n=200000
117	Runtime error	1589 ms	263168 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
118	Halted	0 ms	0 KB	-

답안 #79486

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 18.0 / 18.0

Subtask #3 26.0 / 26.0

Subtask #4 0 / 44.0

Subtask #1
12.0 / 12.0

Subtask #2
18.0 / 18.0

Subtask #3
26.0 / 26.0

Subtask #4
0 / 44.0