글 읽기 - 4% 시간초과

ysyyik 5년 전 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;
}

jh05013 5년 전 0

https://www.acmicpc.net/proble...

cin.tie

ysyyik 5년 전 0

jh05013님 댓글감사합니다만 입출력 문제는 아닌 거 같네요ㅠ

cin.tie(NULL); 추가해봤지만 여전히 시간초과네요..

아마 13번째 줄 find()함수에서 LCA찾는 부분이 문제인 거 같은데..

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

4% 시간초과

ysyyik 5년 전 0

jh05013 5년 전 0

ysyyik 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말