글 읽기 - 반례를 못찾겠습니다 살려주세요

ontael333 4년 전 0

도저히 반례를 못찾겠습니다.

반례좀찾아주시면 감사하겠습니다.

살려주세요 제발

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

struct tree {
	int next;
	long long val;

	tree(int next, long long val) : next(next), val(val) {};
};

vector<tree> v[100001];
int n, m;
int parent[100001][19];
int depth[100001];
bool check[100001];
bool check2[100001];
long long arr[100001];

void func(int x, int cnt) {
	check[x] = true;
	depth[x] = cnt;

	for (int i = 0; i < v[x].size(); i++) {
		if (check[v[x][i].next] == false) {
			parent[v[x][i].next][0] = x;
			func(v[x][i].next, cnt + 1);
		}
	}
}

void dfs(int x) {
	check2[x] = true;

	for (int i = 0; i < v[x].size(); i++) {
		if (check2[v[x][i].next] == false) {
			arr[v[x][i].next] += arr[x] + v[x][i].val;
			dfs(v[x][i].next);
		}
	}
}

int lca(int x, int y) {
	if (depth[x] > depth[y]) {
		int diff = depth[x] - depth[y];
		for (int i = 0; diff; i++) {
			if (diff % 2) {
				x = parent[x][i];
			}
			diff /= 2;
		}
	}
	else if (depth[x] < depth[y]) {
		int diff = depth[y] - depth[x];
		for (int i = 0; diff; i++) {
			if (diff % 2) {
				y = parent[y][i];
			}
			diff /= 2;
		}
	}
	if (x != y) {
		for (int i = 18; i >= 0; i--) {
			if (parent[x][i] && parent[y][i] && parent[x][i] != parent[y][i]) {
				x = parent[x][i];
				y = parent[y][i];
			}
		}
		x = parent[x][0];
	}

	return x;
}

int main() {
	cout.tie(0);
	cin.tie(0);
	std::ios::sync_with_stdio(false);

	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int a, b;
		long long c;
		cin >> a >> b >> c;

		v[a].push_back({ b,c });
		v[b].push_back({ a,c });
	}

	func(1, 0);

	for (int i = 0; i < 19; i++) {
		for (int j = 1; j <= n; j++) {
			if (parent[j][i]) {
				parent[j][i + 1] = parent[parent[j][i]][i];
			}
		}
	}

	dfs(1);

	cin >> m;

	while (m--) {
		int a, b, c, d;
		cin >> a;
		if (a == 1) {
			cin >> b >> c;

			long long dis1 = arr[b];
			long long dis2 = arr[c];

			b = lca(b, c);

			cout << (long long)(dis1 + dis2 - 2 * arr[b]) << "\n";
		}
		else {
			cin >> b >> c >> d;

			int temp_b = b;
			int temp_c = c;
			int dis1 = depth[b];
			int dis2 = depth[c];

			b = lca(b, c);

			dis1 -= depth[b] - 1;

			if (d == dis1) {
				cout << b << "\n";
				continue;
			}
			else if (d < dis1) {
				b = temp_b;
				c = temp_c;
				d--;
				for (int i = 0; d; i++) {
					if (d % 2) {
						b = parent[b][i];
					}
					d /= 2;
				}
				cout << b << "\n";
				continue;
			}
			else {
				c = temp_c;
				d -= dis1;
				d = depth[c] - d;
				for (int i = 0; d; i++) {
					if (d % 2) {
						c = parent[c][i];
					}
					d /= 2;
				}
				cout << c << "\n";
				continue;
			}

		}
	}

	return 0;
}

jaeyoon8783 4년 전 3

오래된 게시물이지만 저도 비슷하게 고통받아서 적어봅니다

19 18 57

15 19 25

8 15 50

1 15 93

12 1 58

10 19 94

13 8 50

14 18 32

20 10 55

4 15 93

2 1 79

17 4 96

3 1 78

6 18 26

16 2 45

7 12 77

5 14 47

11 17 23

9 19 55

2 11 8 5

2 8 11 5

답

오답

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

문제

문제

출처

ICPC

반례를 못찾겠습니다 살려주세요

ontael333 4년 전 0

jaeyoon8783 4년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말