글 읽기 - 출력 초과 질문 ㅜㅠ(시간 초과가 나야 정상이 아닌가요)

pineleaf1215 4년 전 1

//위에서 아래로 오면서 찾아야 된다.

이 부분을 밑에서 위로 찾는 방식으로 제가 바꿔 놓아서 시간 초과가 발생한다면 이해하겠는데

왜 출력초과가 발생하는 것인가요?? ㅠㅠ 이해가 안되서 질문 드립니다.

#include <iostream>
#include <string.h>
#include <cstring>
#include <algorithm>
#include <vector>
#define NUM 100001
int N, K;

using namespace std;

struct edge {
	int node, weight;
};

vector<vector<edge>>adj;
int vis[NUM] = { false };
int depth[NUM] = { 0 };
int mdp[21][NUM] = { -1 };
int sdp[21][NUM] = { -1 };
int dp[21][NUM] = { -1 };

void dfs(edge Edge,int d) {

	vis[Edge.node] = 1;
	depth[Edge.node] = d;

	for (auto iter : adj[Edge.node])
	{
		if (vis[iter.node] == false) {
			mdp[0][iter.node] = Edge.weight;
			sdp[0][iter.node] = Edge.weight;
			dp[0][iter.node] = Edge.node;
			dfs(iter, d + 1);
		}
	}
}


int main() {

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

	freopen("input.txt", "r", stdin);

	memset(mdp, -1, sizeof(mdp));
	memset(sdp, -1, sizeof(sdp));
	memset(dp, -1, sizeof(dp));

	cin >> N;

	adj.resize(N+1);

	for (int i = 0; i < N - 1; i++) {
		int a, b, c=0;

		cin >> a >> b ;//>> c;
		adj[a].push_back(edge{ b ,c});
		adj[b].push_back(edge{ a,c });
	}

	dfs(edge{1,0}, 1);

	for (int i = 1; i < 21; i++) {
		for (int j = 1; j <= N; j++) {
			if(mdp[i-1][j] != -1)
				mdp[i][j] = max(mdp[i][j], mdp[i - 1][mdp[i - 1][j]]);
			if(sdp[i-1][j] != -1)
				sdp[i][j] = min(sdp[i][j], sdp[i - 1][sdp[i - 1][j]]);
			if (dp[i - 1][j] != -1)
				dp[i][j] = dp[i - 1][dp[i-1][j]];
		}
	}

	cin >> K;
	for (int i = 0; i < K; i++) {
		int a, b;
		cin >> a >> b;
		
		if (depth[a] < depth[b]) swap(a, b);
		
		int dis = depth[a]-depth[b];

		
		for (int i = 0; dis; i++,dis /=2) {
			if (dis % 2) {
				a = dp[i][a];
			//	i = 0;
			//	dis -= 1;
			}
		}

		//위에서 아래로 오면서 찾아야된다.
		if (a != b) {
			for (int j = 0; j <= 20; j++) {
				if(dp[j][a] != -1 && dp[j][a] != dp[j][b]){
					a = dp[j][a];
					b = dp[j][b];
				}
			}
			a = dp[0][a];
		}

		//print
		cout << a << "\n";
	}//for



	return 0;
}

kimcoding 4년 전 0

https://www.acmicpc.net/help/judge

출력 초과 부분을 읽어보시면 될 것 같아요.

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

문제

문제

출처

ICPC

출력 초과 질문 ㅜㅠ(시간 초과가 나야 정상이 아닌가요)

pineleaf1215 4년 전 1

kimcoding 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말