a와 b의 상대적인 무게의 차이가 주어진다.
각각의 쿼리에 대해서 c와 d의 차이를 알 수 있는지 판별하고 그 차이를 구하는 문제이다.
처음에는 오프라인 알고리즘을 생각해봤다.
쿼리를 먼저 입력받고 그래프를 구성해서 sparse table을 이용해 $O(nlogn)$에 풀어봤는데 계속 TLE가 났다.
union find로 온라인에 해결할 수 있다.
x의 root까지의 상대적 무게 차이를 dist[x]라 한다면 아래그림과 같이 나타낼 수 있다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
int n, m;
char type;
int a, b, c;
int par[MAXN], sze[MAXN];
ll dist[MAXN];
pair<int, ll> find(int x, ll ret) {
if (x == par[x]) return { x, ret };
return find(par[x], ret + dist[x]);
}
void merge(int a, int b, int t) {
auto x = find(a, 0), y = find(b, 0);
if (x.first == y.first) return;
if (sze[x.first] > sze[y.first]) {
dist[y.first] -= (y.second - x.second - t);
par[y.first] = x.first;
sze[x.first] += sze[y.first];
sze[y.first] = 1;
}
else {
dist[x.first] += (y.second - x.second - t);
par[x.first] = y.first;
sze[y.first] += sze[x.first];
sze[x.first] = 1;
}
}
int main() {
while (scanf("%d%d", &n, &m), !(n == 0 && m == 0)) {
memset(dist, 0, sizeof dist);
for (int i = 1; i <= n; i++) par[i] = i, sze[i] = 1;
for (int i = 0; i < m; i++) {
scanf(" %c", &type);
if (type == '!') {
scanf("%d%d%d", &a, &b, &c);
merge(a, b, c);
}
else {
scanf("%d%d", &a, &b);
auto aa = find(a, 0);
auto bb = find(b, 0);
if (aa.first != bb.first) {
printf("UNKNOWN\n");
}
else {
printf("%lld\n", -aa.second + bb.second);
}
}
}
}
return 0;
}
| cs |
find함수를 다음과 같이 나타낼 수 있다.
이렇게 하면 root까지의 거리 dist[x]를 갱신하면서 root또한 갱신할 수 있다.
int find(int x) {
if (x == par[x]) return x;
int prv = find(par[x]);
dist[x] += dist[par[x]];
return par[x] = prv;
}
| cs |
