oj.uz

Submission #79486

# Submission time Handle Problem Language Result Execution time Memory
79486 2018-10-14T12:16:45 Z JustInCase Birthday gift (IZhO18_treearray) C++17
56 / 100
 2286 ms 263168 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 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

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

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

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