글 읽기 - 아무 반례나 하나만 부탁드려요

p_ce1052 3년 전 0

해볼 수 있는 예제는 많이 해 본 것 같은데 자꾸 틀렸습니다가 뜨네요.

//함수설명

u_find 에서 만약 자신이 곧바로 루트와 연결되어있다면 루트는 자기 자신과의 거리가 0 이므로 어자피 거리갱신이 되지 않을 것이고 만약 루트였던 노드가 다른 노드에 연결되어 루트가 바뀐 상태라면 자신부터 새로운 루트까지의 거리는 부모로부터 새로운 루트까지의 거리를 더해줘야 할 것이므로 더해줍니다.

merge에서는 두 트리를 합칠 때, 한쪽에 속한 a와 다른 한쪽에 속한 b가 있을 때

a와 b의 거리가 w라면

w + dist[b] = dist[a] + a의 루트 ~ b의 루트까지의 거리 " 가 성립해야 하므로

a의 루트에 dist[b]+w-dist[a] 를 넣어주고 p[a의 루트] = b의 루트 로 설정해줍니다.

#include<bits/stdc++.h>
using namespace std;
int p[100005];
long long dist[100005];

int u_find(int a){
	if(p[a]==0) return a;
	int temp = u_find(p[a]);
	dist[a]+=dist[p[a]];
	return p[a] = temp;
}
void merge(int a,int b,int w){
	long long da = dist[a];
	long long db = dist[b];
	a = u_find(a);
	b = u_find(b);
	if(a==b) return;
	p[a] = b;
	dist[a] = db+w-da;
}
int main(){
	//ios_base::sync_with_stdio(false);
	//cin.tie(NULL);
	while(true){
		int n,m;
		cin>>n>>m;
		if(!n && !m) return 0;
		while(m--){
			char ch;
			long long a,b,w;
			cin>>ch;
			if(ch=='!'){
				cin>>a>>b>>w;
				merge(a,b,w);
			}
			else{
				cin>>a>>b;
				if(u_find(a)!=u_find(b)) cout<<"UNKNOWN"<<'\n';
				else{
					cout<<dist[a]-dist[b]<<'\n';
				}
			}
		}
		for(int i=1; i<=n; i++) p[i] = 0; 
		for(int i=1; i<=n; i++) dist[i] = 0;
	}
}

roonm813 3년 전 11

반례입니다.

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

문제

문제

출처

ICPC

아무 반례나 하나만 부탁드려요

p_ce1052 3년 전 0

roonm813 3년 전 11

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말