글 읽기 - SPOJ

jongseo_park 4년 전 0

https://www.acmicpc.net/board/view/10349

여기에서 말한대로 저기에서는 맞았다고 나와서 그 아래 써있는대로 long long으로 몇개 변수를 바꿔줬는데, 여전히 틀렸다고 하네요...

다른 차이점이 있나요?

#include<cstdio>
#include<cstdlib>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstring>

#define _1 first
#define _2 second

using namespace std;

void arrscanf(const char* a, bool* b, int c) {
	for (int i = 0; i < c; i++)
		scanf(a, b + i);
}
void arrscanf(const char* a, short* b, int c) {
	for (int i = 0; i < c; i++)
		scanf(a, b + i);
}
void arrscanf(const char* a, int* b, int c) {
	for (int i = 0; i < c; i++)
		scanf(a, b + i);
}
void arrscanf(const char* a, long long* b, int c) {
	for (int i = 0; i < c; i++)
		scanf(a, b + i);
}
void arrscanf(const char* a, double* b, int c) {
	for (int i = 0; i < c; i++)
		scanf(a, b + i);
}
void arrscanf(const char* a, long double* b, int c) {
	for (int i = 0; i < c; i++)
		scanf(a, b + i);
}
void arrscanf(const char* a, pair<int, int>* b, int c) {
	for (int i = 0; i < c; i++)
		scanf(a, &b[i]._1, &b[i]._2);
}
//이 위의 함수는 편의성을 위함, 신경쓸 필요 없음
//호출 횟수 0번

int n, m, x, y, z, p[30][100001], lvl[100001];
long long cst[100001];
vector<pair<int, long long>>v[100001];

int pfind(int level, int index) {
	if (level == 0)
		return index;
	for (int i = 0; i < 30; i++)
		if ((level >> i) % 2)
			return pfind(level - (1 << i), p[i][index]);
}
//index의 level번째 부모 찾기

void treeorg(int level, int index, int parent, int cost) {
	p[0][index] = parent;
	lvl[index] = level;
	cst[index] = cost;
	int tmp = v[index].size();
	for (int i = 0; i < tmp; i++) {
		if (v[index][i]._1 == parent)
			continue;
		treeorg(level + 1, v[index][i]._1, index, cost + v[index][i]._2);
	}
}
//시작할때 index의 lvl값을 level로 설정하고 p[0][index]를 parent로 설정, cst[index]를 cost로 설정
//또한 자식 노드들에게 저 4개의 값을 전달

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n - 1; i++) {
		int tmp1, tmp2;
		long long tmp3;
		scanf("%d%d%lld", &tmp1, &tmp2, &tmp3);
		v[tmp1].push_back({ tmp2,tmp3 });
		v[tmp2].push_back({ tmp1,tmp3 });
	} //입력
	treeorg(0, 1, 1, 0); //1을 루트로 설정하고 함수 호출
	for (int i = 1; i < 30; i++)
		for (int j = 1; j <= n; j++)
			p[i][j] = p[i - 1][p[i - 1][j]]; //p배열 설정
	scanf("%d", &m); //쿼리 개수 입력
	while (m--) {
		int tmp;
		scanf("%d%d%d", &tmp, &x, &y); //1/2, u,v
		if (tmp == 2) {
			scanf("%d", &z); //t
			z -= 1;
		}
		int lv = min(lvl[x], lvl[y]);
		int x1 = pfind(lvl[x] - lv, x);
		int y1 = pfind(lvl[y] - lv, y); //같은 레벨로 맞춰주기
		if (x1 != y1) { //둘중 하나가 나머지 하나의 부모가 아닌 경우
			for (int i = 29; i > -1; i--) {
				if (p[i][x1] != p[i][y1]) {
					x1 = p[i][x1];
					y1 = p[i][y1];
				}
			} //공통부모 아랫 단계 찾기
			if (tmp == 1)
				printf("%lld\n", (cst[x] + cst[y] - (2 * cst[p[0][x1]]))); //1인경우
			if (tmp == 2) {
				if (z > (lvl[x] - (lvl[x1] - 1)))
					printf("%d\n", pfind(lvl[y] - (lvl[x1] - 1) + (((lvl[x] - (lvl[x1] - 1)) - z)), y));//2인경우, u에서 최소공통부모 이전
				else
					printf("%d\n", pfind(z, x)); //2인경우 u에서 최소공통부모 이후
			}
		}
		else if (tmp == 1)
			printf("%lld\n", (cst[x] + cst[y] - (2 * cst[x1]))); //둘중 하나가 나머지 하나의 부모인 경우
		else if (tmp == 2) {
			if (z > (lvl[x] - lvl[x1])) //2인경우
				printf("%d\n", pfind(lvl[y] - (lvl[x1]) + (((lvl[x] - (lvl[x1])) - z)), y));
			else
				printf("%d\n", pfind(z, x));
		}
	}
	return 0;
}

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

문제

문제

출처

ICPC

SPOJ

jongseo_park 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말