백준3830 교수님은 기다리지 않는다

작성일 | In

문제 링크

  • http://icpc.me/3830

문제 출처

  • 2012 Tkoyo Regional F번

사용 알고리즘

  • Union-Find

풀이

온라인 처리와 오프라인 처리를 모두 사용하는 재밌는 풀이입니다.
impossible을 출력하는 것은 온라인으로 판단하고, 나머지는 오프라인으로 계산합니다.

impossible을 판단하는 것은 union find로 쉽게 처리가 가능합니다.
u, v의 비교 결과가 주어질 때, u와 v가 연결되어있지 않다면(같은 집합에 속하지 않는다면) merge해주고, 간선을 추가해줍니다.
위와 같이 merge를 하고 간선을 잘 추가해줬다면, impossible은 두 정점이 서로 다른 집합에 속해있는지만 판단해주면 됩니다.

무게 차이 계산은 트리에서 두 정점의 거리를 계산하는 느낌으로 할 수 있습니다.
임의의 정점을 루트로 고정을 시켜봅시다. 저는 1로 고정했습니다.
b가 a보다 얼마나 무거운지 계산하는 것은, (루트가 a보다 얼마나 무거운지) 계산한 결과와 (b가 루트보다 얼마나 무거운지) 계산한 결과를 더해준 값이 됩니다.
dist[v] = v의 무게 - 루트의 무게 라고 정의해서 dist배열을 미리 계산했다면, 정답은 dist[b] - dist[a] 로 쉽게 구할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

int n, q;

struct Query{
	int s, e;
	Query(){}
	Query(int s, int e) : s(s), e(e) {}
};

ll dist[101010];
vector<p> g[101010];
int par[101010];
int chk[101010];
int im[101010];
vector<Query> qry;

int find(int v){
	return v == par[v] ? v : par[v] = find(par[v]);
}

bool merge(int u, int v){
	u = find(u), v = find(v);
	if(u == v) return 0;
	par[u] = v;
	return 1;
}

void dfs(int v, ll d){
	chk[v] = 1;
	dist[v] = d;
	for(auto i : g[v]){
		int nxt = i.first;
		if(chk[nxt]) continue; chk[nxt] = 1;
		dfs(nxt, d + i.second);
	}
}

void init(){
	for(int i=0; i<101010; i++) par[i] = i, dist[i] = 0, g[i].clear(), chk[i] = 0, im[i] = 0;
	qry.clear();
}

void solve(){
	init();
	for(int i=1; i<=q; i++){
		char op; cin >> op;
		if(op == '!'){
			int a, b, c; cin >> a >> b >> c;
			if(merge(a, b)){
				g[a].emplace_back(b, c);
				g[b].emplace_back(a, -c);
			}
		}else{
			int a, b; cin >> a >> b;
			qry.emplace_back(a, b);
			if(find(a) != find(b)){
				im[qry.size()-1] = 1;
			}
		}
	}
	for(int i=1; i<=n; i++){
		if(!chk[i]) dfs(i, 0);
	}
	for(int i=0; i<qry.size(); i++){
		int s = qry[i].s;
		int e = qry[i].e;
		if(im[i]){
			cout << "UNKNOWN\n"; continue;
		}
		cout << dist[e] - dist[s] << "\n";
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	while(1){
		cin >> n >> q;
		if(!n && !q) break;
		solve();
	}
}