Submission #79487

#	Time	Username	Problem	Language	Result	Execution time	Memory
79487		JustInCase	Birthday gift (IZhO18_treearray)	C++17	100 / 100	2538 ms	117124 KiB

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 / 12
• Subtask 2: 18 / 18
• Subtask 3: 26 / 26
• Subtask 4: 44 / 44