BOJ 16182 - Dumae (D5)

사용 알고리즘

Greedy(pq) + Topological Sorting

 

풀이

일단 자명하게 DAG가 아니면 -1이다.

그래프의 순서 관계도 있고 [L,R] 조건도 있어서 까다로울 수 있다. 결론부터 말하면 이 둘을 합치면 된다.



위부터 1,2,3번 노드로 가정

대충 이런 그래프가 있다고 하자. 여기서 1번 노드는 자기만 보면 1번째 순서가 될 수도 있고 2번째 순서가 될 수도 있다. 하지만 바로 아래 노드(2번)를 고려하면 반드시 1번째 순서가 되어야 함을 알 수 있다. 이 조건을 [L,R]로 표현하려면 어떻게 해야 할까?

위 상황에서 $R_2=2$이다. 그 말은 2번 노드는 2번째 순서 안에 선택되어야 한다. 그리고 2번 노드가 선택되려면 1번 노드를 먼저 골랐어야 하므로 적어도 1번 노드는 2번째 순서보다 한칸 앞선 1번째 순서 안에 선택되었어야 한다. 이는 자명해 보이지만 [L,R] 조건을 강화시키는 중요한 단서가 된다. 정리하면 u->v 간선이 있을 때 $R_u=max(R_u,R_v-1)$라는 사실을 알 수 있다.

이렇게 R 조건을 강화한 상태에서 스케줄링 느낌의 그리디를 위상정렬하면서 수행하면 된다. L 조건은 굳이 강화할 필요가 없다는 사실은 자명하므로 생략.

 

#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 100000
#define MOD2 998244353
#define debug(x) cout << #x<<" is "<<x<<"\n";
#define X first
#define Y second
#define DEB cout<<"[DEBUG]"
#define PAIR(a,b) "("<<a<<", "<<b<<")"
#define PRINT1(V) DEB<<#V<<endl; for(auto i : V)DEB<<i<<"\n"
#define PRINT2(V) DEB<<#V<<endl; for(auto [a,b] : V)DEB<<PAIR(a,b)<<"\n";
typedef long long ll;
typedef __int128_t lll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
ll n, m;
vector<ll> adj[303030], rdj[303030];
ll ind[303030], outd[303030];
vector<P> v;
vector<ll> r;
ll ans[303030];
vector<ll> que[303030];
int main(){
    fast;
    cin>>n>>m;
    v.resize(n); r.resize(n);
    for(auto &[a,b] : v)cin>>a>>b;
    for(int i = 0 ; i < m ; i++){
        ll a,b; cin>>a>>b; a--; b--;
        adj[a].push_back(b); ind[b]++;
        rdj[b].push_back(a); outd[a]++;
    }
    queue<ll> q;
    for(int i = 0 ; i < n ; i++){
        if(!outd[i])q.push(i);
        r[i] = v[i].Y;
    }
    for(int i = 0 ; i < n ; i++){
        if(q.empty())return !(cout<<-1);
        ll x = q.front(); q.pop();
        for(auto next : rdj[x]){
            r[next] = min(r[next], r[x]-1);
            if(--outd[next] == 0)q.push(next);
        }
    }
    priority_queue<P> pq;
    for(int i = 0 ; i < n ; i++){
        if(!ind[i])que[max(1LL,v[i].X)].push_back(i);
    }
    for(ll i = 1 ; i <= n ; i++){
        for(auto next : que[i])pq.push({-r[next],next});
        if(pq.empty())return !(cout<<-1);
        auto [R,x] = pq.top(); pq.pop(); R=-R;
        if(i>R)return !(cout<<-1);
        ans[i] = x+1;
        for(auto next : adj[x]){
            if(--ind[next] == 0)que[max(i+1,v[next].X)].push_back(next);
        }
    }
    for(int i = 1 ; i <= n ; i++)cout<<ans[i]<<"\n";
}

L 조건을 잘못 구현해서 2틀