oj.uz

Submission #79487

# Submission time Handle Problem Language Result Execution time Memory
79487 2018-10-14T12:18:25 Z JustInCase Birthday gift (IZhO18_treearray) C++17
100 / 100
 2538 ms 117124 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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