글 읽기 - 시간초과 ..

goodksj 7년 전 0

제 알고리즘에서 시간을 줄일 수 있는 방법이 무엇일까요?ㅠㅠ

#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

long long N, x, y, K, Q;


bool decision(long long a, int p){
	return a <= ((pow(K, p) - 1) / (K -1));
}
int getDepth(long long a){
	int lo = 0, hi = 1001;
	int mid;
	for(int i = 0; i < 13; i++){
		mid = (hi + lo) / 2;
		if(decision(a, mid)){
			hi = mid;	
		}
		else{
			lo = mid;
		}
	}
	return hi;
}



long long getParent(long long a){
	return (a + K - 2) / K;
}
int main(){
	freopen("input.txt","r",stdin);
	setbuf(stdout, NULL);


	scanf("%lld %lld %lld", &N, &K, &Q);
	// K = 3;
	// cout<<K<<endl;
	
	// cout<<getDepth(4)<<endl;
	int d;
	int x_depth, y_depth;
	for(int i = 0 ; i < Q; i++){

		scanf("%lld %lld", &x, &y);

		d = 0;
		x_depth = getDepth(x);	y_depth = getDepth(y);
		if(x_depth > y_depth){
			d += x_depth - y_depth;
			for(int j = 0; j < x_depth - y_depth; j++)
				x = getParent(x);
		}
		else if(y_depth > x_depth){
			d += y_depth - x_depth;
			for(int j = 0; j < y_depth - x_depth; j++)
				y = getParent(y);
		}

		while(x != y){
			y = getParent(y);
			x = getParent(x);
			d += 2;
		}
		printf("%d\n", d);
	}

	return 0;
}

topology 6년 전 0

k = 1일때 너무 시간이 오래걸릴 것 같네요.

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

문제

문제

출처

ICPC

시간초과 ..

goodksj 7년 전 0

topology 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말