글 읽기 - 4% 시간초과

(追記) (追記ここまで)

4% 시간초과

10838번 - 트리

ysyyik 7년 전 0

O(n) 으로 계산되게 다 맞췄는데 왜 시간초과가 날까요..

도저히 찾을 수가 없어서 질문합니다ᅲ

// 10838_트리.cpp
#include <iostream>
#include <vector>
#include <set>
using namespace std;
//vector<pair<int, int>> tree;	// index: node#, first: parent, second: weight
pair<int, int> tree[100001];
int visit[100001];				// LCA를 탐색하기 위해 방문여부 체크
int n, k, r, a, b, c;
int find(int a, int b) {		// LCA 탐색
	if (a == b)					// 없어서 런타임에러 났던 부분1
		return a;
	visit[a] = a;
	visit[b] = b;
	int ap = tree[a].first;
	int bp = tree[b].first;
	while (ap != -1) {
		if (visit[ap] == b) {
			return ap;
		}
		visit[ap] = a;
		ap = tree[ap].first;
	}
	while (bp != -1) {
		if (visit[bp] == a) {
			return bp;
		}
		bp = tree[bp].first;
	}
	return 0;
}
void paint(int a, int b, int c) {
	if (a == b)
		return;
	int p = find(a, b);			// LCA 탐색
	while (a != p) {
		tree[a].second = c;
		a = tree[a].first;
	}
	while (b != p) {
		tree[b].second = c;
		b = tree[b].first;
	}
}
void move(int a, int b) {
	if (a == b)
		return;
	tree[a].first = b;
}
void count(int a, int b) {
	if (a == b) {
		cout << 0 << '\n';
		return;
	}
	set<int> color;						// 중복되지 않는 색깔 개수 저장
	int p = find(a, b);					// p = lca
	while (a != p) {					// a에서 lca까지 올라가면서 color 기록
		color.insert(tree[a].second);
		a = tree[a].first;				// a <- 부모 노드로 교체
	}
	while (b != p) {					// b에서 lca까지 올라가면서 color 기록
		color.insert(tree[b].second);
		b = tree[b].first;				// b <- 부모 노드로 교체
	}
	cout << color.size() << '\n';		// 결과 출력
	//color.clear();					// 다음 번 호출을 위한 초기화
}
int main() {
	std::ios::sync_with_stdio(false);
	cin >> n >> k;
	//tree.assign(n, pair<int, int>(0, 0));
	tree[0] = { -1, -1 };
	while (k--) {
		cin >> r >> a >> b;
		switch (r) {
		case 1:
			cin >> c;
			paint(a, b, c);
			break;
		case 2:
			move(a, b);
			break;
		case 3:
			count(a, b);
			break;
		}
	}
	return 0;
}