글 읽기 - 런타임(Out of Bounds)

dbsgkdud136 2년 전 0

제 로컬에서는 잘 실행되는데 제출하면 범위를 벗어났다고 합니다 ㅜㅜ

찾아주시면 정말정말 정말정말 감사하겠습니다..!!

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

vector<int> get_input[100001];
int depth[100001];
int parent[100001][21];
int n, m, a, b;


void dfs(int cur) {
	int next;
	for (int i = 0; i < get_input[cur].size(); i++) {
		next = get_input[cur][i];
		if (depth[next] == -1) {
			parent[next][0] = cur;
			depth[next] = depth[cur] + 1;
			dfs(next);
		}
	}
	return;
}


void connection() {
	for (int k = 1; k < 21; k++) {
		for (int cur = 1; cur <= n; cur++) {
			parent[cur][k] = parent[parent[cur][k-1]][k - 1];
		}
	}
	return;
}


int lca(int u, int v) {
	if (depth[u] < depth[v]) {
		swap(u, v);
	}

	int diff = depth[u] - depth[v];

	for (int i = 0; diff != 0; ++i) {
		if (diff % 2 == 1) {
			u = parent[u][i];
		}
		diff = diff / 2;
	}

	if (u != v) {
		for (int i = 20; i >= 0; --i) {
			if (parent[u][i] != -1 && parent[u][i] != parent[v][i]) {
				u = parent[u][i];
				v = parent[v][i];
			}
		}
		u = parent[u][0];
	}
	return u;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	fill(depth, depth + n + 1, -1);
	memset(parent, -1, sizeof(parent));
	depth[1] = 0;


	
	for (int i = 0; i < n - 1; i++) {
		cin >> a >> b;
		get_input[a].push_back(b);
		get_input[b].push_back(a);
	}

	dfs(1);
	connection();
	

	cin >> m;
	
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		cout<< lca(a, b)<<"\n";

	}

	return 0; 

} 

jsj032097 9달 전 0

혹시 왜 틀리셨나요? 같은 오류가 납니다ㅠ

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

문제

문제

출처

ICPC

런타임(Out of Bounds)

dbsgkdud136 2년 전 0

jsj032097 9달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말