4016번: 모빌

https://www.acmicpc.net/problem/4016


$O(n)$

임의의 막대에 대해 장난감들의 최대 레벨 차이가 1이하이며 왼편과 오른편 둘 중 적어도 하나는 장난감들의 레벨 차이가 없어야 한다.
왼편의 최소 레벨이 오른편의 최대 레벨보다 작다면 서로 바꿔준다.

#include<cstdio>
const int MXN = 1e5;
int n, l[MXN + 1], r[MXN + 1], lo[MXN + 1], hi[MXN + 1], cnt;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d%d", l + i, r + i);
    for (int i = n; i; i--) {
        int tl = l[i] < 0 ? 0 : l[i], tr = r[i] < 0 ? 0 : r[i];
        if (lo[tl] < hi[tr]) tl ^= tr ^= tl ^= tr, cnt++;
        lo[i] = lo[tr] + 1;
        hi[i] = hi[tl] + 1;
        if (lo[tl] < hi[tr] || hi[i] - lo[i]>1) {
            puts("-1");
            return 0;
        }
    }
    printf("%d", cnt);
    return 0;
}