글 읽기 - 15563 Äventyr 1 웰노운컵 문제 도와주세요

dlftls38 4년 전 0

15564 Äventyr 1 를 먼저 풀어보았지만

N이 10^5일때 트리 노드간의 거리를 구하는 법을 아무리 찾아봐도 모르겠어서 15563부터 풀어보자 했습니다.

아무리 문제를 읽어봐도 15564와 차이가 없었는데 잘 보니 1열로 이루어진 트리더군요 그래서 간단하게 짜서 제출해봤는데 틀렸다고나옵니다.

제가 문제를 잘못해석한건가요..

트리의 노드 거리를 빠르게 구하는 알고리즘이 존재하나요?

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <limits.h>
#include <functional>
#include <math.h>
#include <fstream>
#define INF 987654321
#define MAX_VALUE 1000000000
#define MOD 1000000009
using namespace std;
typedef pair<int,int> pii;
int main(){
	int n,q;
	scanf("%d%d",&n,&q);
	int i,j;
	for(i=2;i<=n;i++){
		int temp;
		scanf("%d",&temp);
	}
	set<int>s;
	for(i=0;i<q;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		if(a==1){
			s.insert(b);
		}
		else{
			if(s.size()==0){
				printf("-1\n");
			}
			else if(s.size()==1){
				printf("%d\n",abs(b-*s.begin()));
			}
			else{
				auto it=s.upper_bound(b);
				auto right = abs(b-*(it));
				auto left = abs(b-*(--it));
				printf("%d\n",min(right,left));
			}
		}
	}
}

sait2000 4년 전 1

일단 43~46에서 오른쪽이나 왼쪽이 존재한다는 보장이 없습니다. 바이올린이 전부 왼쪽에.있거나 오른쪽에 있을 수 있으니까요

2는 저도 모릅니다. centroid decomposition이라는 걸로 알고있는데 공부도 안 해봤고요...

dlftls38 4년 전 0

감사합니다 말씀 듣고 고쳐봤습니다. 제가 이해한 바로는 시간축이 일렬로 되어있기에 모든 경우를 충족한다 생각했는데 틀렸네요

혹시 제가 문제를 잘못 이해하고있는건가요?

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <limits.h>
#include <functional>
#include <math.h>
#include <fstream>
#define INF 987654321
#define MAX_VALUE 1000000000
#define MOD 1000000009
using namespace std;
typedef pair<int,int> pii;
int main(){
	int n,q;
	scanf("%d%d",&n,&q);
	int i,j;
	for(i=2;i<=n;i++){
		int temp;
		scanf("%d",&temp);
	}
	set<int>s;
	for(i=0;i<q;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		if(a==1){
			s.insert(b);
		}
		else{
			if(s.size()==0){
				printf("-1\n");
			}
			else{
				auto it=s.lower_bound(b);
				if(it==s.end()){
					printf("%d\n",abs(b-*(--it))); // 전부 왼쪽에 있을 때 
				}
				else{
					if(s.size()==1){
						printf("%d\n",abs(b-*it)); // 현 위치를 포함해서 오른쪽에 하나 있을 때 
					}
					else{ // 두개 이상 있을 때 
						if(it==s.begin()){
							printf("%d\n",abs(b-*it)); // 가장 가까운 것이 자명 할 때 
						}
						else{
							printf("%d\n",min(abs(b-*it),abs(b-*(--it)))); // 현 위치를 포함해 오른쪽에 하나, 그 왼쪽 하나 비교 
						}
					}
				}
			}
		}
	}
}

sait2000 4년 전 1

53번 줄에 있는 두개의 값이 --가 있어서 잘못 나올 수있을 것 같네요 각각을 변수에 대입한 다음 최소값을 구해보세요 그래도 틀리면 잘 모르겠네요

dlftls38 4년 전 0

그 부분을 고치니 맞네요

정말 감사합니다 엄청나시군요!

같은 라인에 --가있어서 잘못 될 수 있나 보군요 정말 감사합니다!

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

문제

문제

출처

ICPC

15563 Äventyr 1 웰노운컵 문제 도와주세요

dlftls38 4년 전 0

sait2000 4년 전 1

dlftls38 4년 전 0

sait2000 4년 전 1

dlftls38 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말