백준2927 남극 탐험

작성일 | In

문제 링크

  • http://icpc.me/2927

문제 출처

  • 2009 COI 2번

사용 알고리즘

  • HLD
  • 유니온 파인드
  • 세그 트리

풀이

HLD 문제라는 것은 쉽게 알 수 있습니다.

주의해야 할 점이 있는데, 주어진 그래프가 연결되어있지 않을 수 있습니다.
다양한 해결방법이 존재하는데, 저는 1번 정점에서 갈 수 없는 정점들은 1번 정점과 연결해주었습니다.
그러면 하나의 트리에서 hld를 돌려서 비교적 편하게 해결할 수 있습니다.

전체 코드

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <bits/stdc++.h>
using namespace std;

struct UF{
	int par[30303];
	UF(){
		for(int i=0; i<30303; i++) par[i] = i;
	}
	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;
	}
};

struct Seg{
	int tree[1 << 18];
	int bias = 1 << 17;

	void update(int x, int v){
		x |= bias; tree[x] = v;
		while(x >>= 1){
			tree[x] = tree[x << 1] + tree[x << 1 | 1];
		}
	}

	int query(int l, int r){
		l |= bias, r |= bias;
		int ret = 0;
		while(l <= r){
			if(l & 1) ret += tree[l++];
			if(~r & 1) ret += tree[r--];
			l >>= 1, r >>= 1;
		}
		return ret;
	}
}seg;

vector<int> inp[30303], g[30303];
int par[30303], sz[30303], top[30303], dep[30303], in[30303];
int arr[30303], chk[30303];
int pv;
int n, q;

void dfs(int v = 1){
	chk[v] = 1;
	for(auto i : inp[v]){
		if(chk[i]) continue;
		chk[i] = 1;
		g[v].push_back(i);
		dfs(i);
	}
}

void dfs1(int v = 1){
	for(auto &i : g[v]){
		par[i] = v;
		dep[i] = dep[v] + 1;
		dfs1(i);
		sz[v] += sz[i];
		if(sz[i] > sz[g[v][0]]) swap(i, g[v][0]);
	}
}

void dfs2(int v = 1){
	in[v] = ++pv;
	for(auto &i : g[v]){
		top[i] = i == g[v][0] ? top[v] : i;
		dfs2(i);
	}
}

void update(int x, int v){
	seg.update(in[x], v);
}

int query(int a, int b){
	int ret = 0;
	while(top[a] != top[b]){
		if(dep[top[a]] < dep[top[b]]) swap(a, b);
		int st = top[a];
		ret += seg.query(in[st], in[a]);
		a = par[st];
	}
	if(dep[a] > dep[b]) swap(a, b);
	ret += seg.query(in[a], in[b]);
	return ret;
}

struct Query{
	string op; int a, b;
};
vector<Query> qry;

int main(){
	top[1] = dep[1] = 1;
	ios_base::sync_with_stdio(0); cin.tie(0);
	UF uf;
	cin >> n;
	for(int i=1; i<=n; i++) cin >> arr[i];

	cin >> q;

	while(q--){
		string op; int a, b; cin >> op >> a >> b;
		qry.push_back({op, a, b});
		if(op == "bridge"){
			if(uf.merge(a, b)) inp[a].push_back(b), inp[b].push_back(a);
		}
	}
	for(int i=1; i<=n; i++){
		if(uf.merge(1, i)){
			inp[1].push_back(i); inp[i].push_back(1);
		}
	}

	dfs(); dfs1(); dfs2();
	for(int i=1; i<=n; i++) update(i, arr[i]);
	for(int i=0; i<30303; i++) uf.par[i] = i;

	for(auto i : qry){
		if(i.op == "bridge"){
			if(uf.merge(i.a, i.b)) cout << "yes\n";
			else cout << "no\n";
		}else if(i.op == "penguins"){
			update(i.a, i.b);
		}else{
			if(uf.find(i.a) != uf.find(i.b)) cout << "impossible\n";
			else cout << query(i.a, i.b) << "\n";
		}
	}
}