[충남대 SW-IT 2025] Designing a Tree

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

 

문제가 깔끔하다.

 

풀이도 깔끔하다.

 

술ㅍ마시고 푸니까 기분이 좋다.

벌써 입대가 이번 달로 다가왔다. ㅅㅂ

 

일단 $N$은 반드시 전체 트리의 루트가 되어야 한다.

그 다음에 $N$을 포함하는 모든 구간은 $N$이 부모 정점이 되도록 잇지 않을 이유가 없다.

 

따라서 구성하고 있는 트리에 연결을 완료한 정점에 대해, 그 정점을 포함하는 구간을 갖는 모든 정점을 다음 잇는 정점의 대상으로 본다.

 

세그먼트 트리에서 구간 업데이트 + 단일 쿼리에서 구간을 갖는 모든 노드에 벡터를 대응한 후 빼낼 때마다 벡터를 비워주면 구현할 수 있다.

 

플래2인듯?

 

#include <bits/stdc++.h>
using namespace std; using ll = long long; using ii = pair<ll,ll>; using vi = vector<ll>;
#define rep(i,a,b) for (ll i = (a); i <= (b); ++i)
#define per(i,a,b) for (ll i = (b); i >= (a); --i)
#define all(x) (x).begin(), (x).end()
#define siz(x) ll((x).size())
#define Mup(x,y) (x = max(x,y))
#define mup(x,y) (x = min(x,y))
#define fi first
#define se second
#define pb push_back
#define dbg(...) fprintf(stderr,__VA_ARGS__)
#define int do not use int

template <class T, const ll N> struct RUPQ {
    ll n; T t[2*N];
    void set(ll _n, T e) { n=_n, fill(t,t+2*n,e); }
    void update(ll a, ll b, ll v) {
        assert(0 <= a and a-1 <= b and b < n);
        for (a += n, b += n; a <= b; ++a /= 2, --b /= 2) {
            if (a&1) t[a].pb(v);
            if (~b&1) t[b].pb(v);
        }
    }
    vi query(ll k) {
        assert(0 <= k and k < n);
        vi s;
        for (k += n; k >= 1; k /= 2) {
            s.insert(s.end(), all(t[k]));
            t[k].clear();
        }
        return s;
    }
};

const ll N = 5e5 + 3;
ll n;
RUPQ<vi, N> ds;
bool conn[N];
ll ans[N];

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    ds.set(n+1, {});
    rep(i,1,n-1) {
        ll l, r;
        cin >> l >> r;
        ds.update(l, r, i);
    }
    conn[n] = 1;
    
    queue<ll> Q;
    Q.push(n);
    
    while(!empty(Q)) {
        ll s=Q.front(); Q.pop();
        auto v = ds.query(s);
        
        for(auto i:v) {
            if(conn[i])continue;
            conn[i]=true;
            Q.push(i);
            
            ans[i] = s;
        }
    }
    
    rep(i,1,n) {
        if(not conn[i]) {
            cout << "NO";
            return 0;
        }
    }
    
    cout << "YES\n";
    rep(i,1,n-1) cout << ans[i] << ' ';
}