글 읽기 - 이건 무슨 경우일까요...?

kangi96 4년 전 0

두 코드는 딱 한 줄만 다릅니다.

e -= (dist[cur]-dist[nxt]); // WA

e -= nxt_e; // AC

하지만 int nxt_e=dist[cur]-dist[nxt];이라고 정의했기 때문에 틀려야 할 이유가 없는 것 같은데 무엇이 문제인지 잘 모르겠습니다.

도움주시면 감사하겠습니다.

#include <bits/stdc++.h>
#define MAX 100000
#define MAX_I 17

using namespace std;

typedef vector<vector<pair<int,int> > > VP;

int n,par[MAX+1][MAX_I],dist[MAX+1],energy[MAX+1];
VP adj;

void dfs(int cur){
	for(auto p: adj[cur]){
		int nxt=p.first;
		if(dist[nxt]==-1){
			dist[nxt] = dist[cur]+p.second;
			par[nxt][0] = cur;
			dfs(nxt);
		}
	}
}

int main(){
	int u,v,w;
	memset(par,-1,sizeof(par));
	memset(dist,-1,sizeof(dist));
	adj.resize(MAX+1);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)	scanf("%d",&energy[i]);
	for(int i=1;i<n;i++){
		scanf("%d %d %d",&u,&v,&w);
		adj[u].push_back(make_pair(v,w));
		adj[v].push_back(make_pair(u,w));
	}
	dist[1] = 0;
	dfs(1);
	for(int j=1;j<MAX_I;j++){
		for(int i=1;i<=MAX;i++){
			if(par[i][j-1]!=-1)	par[i][j] = par[par[i][j-1]][j-1];
		}
	}
	for(int i=1;i<=n;i++){
		int cur=i,e=energy[i];
		for(int j=MAX_I-1;j>=0;j--){
			int nxt=par[cur][j];
			int nxt_e=dist[cur]-dist[nxt];
			if(nxt==-1 || e<nxt_e)	continue;
			cur = nxt;
			e -= nxt_e;
		}
		printf("%d\n",cur);
	}
	return 0;
}
// AC 처리 된 코드

#include <bits/stdc++.h>
#define MAX 100000
#define MAX_I 17

using namespace std;

typedef vector<vector<pair<int,int> > > VP;

int n,par[MAX+1][MAX_I],dist[MAX+1],energy[MAX+1];
VP adj;

void dfs(int cur){
	for(auto p: adj[cur]){
		int nxt=p.first;
		if(dist[nxt]==-1){
			dist[nxt] = dist[cur]+p.second;
			par[nxt][0] = cur;
			dfs(nxt);
		}
	}
}

int main(){
	int u,v,w;
	memset(par,-1,sizeof(par));
	memset(dist,-1,sizeof(dist));
	adj.resize(MAX+1);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)	scanf("%d",&energy[i]);
	for(int i=1;i<n;i++){
		scanf("%d %d %d",&u,&v,&w);
		adj[u].push_back(make_pair(v,w));
		adj[v].push_back(make_pair(u,w));
	}
	dist[1] = 0;
	dfs(1);
	for(int j=1;j<MAX_I;j++){
		for(int i=1;i<=MAX;i++){
			if(par[i][j-1]!=-1)	par[i][j] = par[par[i][j-1]][j-1];
		}
	}
	for(int i=1;i<=n;i++){
		int cur=i,e=energy[i];
		for(int j=MAX_I-1;j>=0;j--){
			int nxt=par[cur][j];
			int nxt_e=dist[cur]-dist[nxt];
			if(nxt==-1 || e<nxt_e)	continue;
			cur = nxt;
			e -= (dist[cur]-dist[nxt]);
		}
		printf("%d\n",cur);
	}
	return 0;
}

// WA 처리 된 코드

kangi96 4년 전 0

혹시 몰라서 e = e-(dist[cur]-dist[nxt]);이렇게도 해봤는데 역시 WA를 받았습니다. 컴파일러 단계의 문제인가요? 이런 경우가 없어서 정말 궁금하네요

crypt9 4년 전 0

cur=10, nxt=20 이라 가정하면,

// cur 과 nxt 를 계산

int nxt_e=dist[cur]-dist[nxt]; // dist[10] - dist[20]

cur = nxt; // cur = 20

e -= nxt_e; // e -= dist[10]-dist[20]

// nxt 와 nxt 를 계산

int nxt_e=dist[cur]-dist[nxt]; // dist[10] - dist[20]

cur = nxt; // cur = 20

e -= (dist[cur]-dist[nxt]); // e-= dist[20] - dist[20]

kangi96 4년 전 0

허허...과거의 저는 무지했었군요 오랜만에 다시 보니 부끄럽네요ㅎㅎ답변 감사합니다

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

문제

문제

출처

ICPC

이건 무슨 경우일까요...?

kangi96 4년 전 0

kangi96 4년 전 0

crypt9 4년 전 0

kangi96 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말