BOJ 15758 - Milking Order

BOJ 15758 - Milking Order

단순히 이분탐색을 써서 $X$를 구한다음 해당 $X$에서 정답을 구성할 땐 방문될 수 있는 것 중 가장 앞선 번호를 먼저 방문하도록 우선순위 큐로 해주고 아예 방문되지 않은 것들을 정답에 사전순으로 가장 빠르게 끼워넣는 방법을 쓰면 된다.

$O(n \log^2 n)$ 에 쉽게 풀리는 문제이며 USACO 문제인데도 이전 시즌이라 그런지 아이디어가 많이 필요하지 않아서 편안히 풀 수 있었다.

void solve() {  
   int n, m;  
   cin >> n >> m;  
   vvi ob(m);  
   for (int i = 0; i < m; i++) {  
      int k;  
      cin >> k;  
      ob[i].resize(k);  
      fv(ob[i]);  
      for (int &i: ob[i]) i--;  
   }  
   int l = 1, r = m, ret = -1;  
  
   auto chk = [&](int limit) -> bool {  
      vvi edges(n);  
      vi in(n);  
      for (int i = 0; i < limit; i++) {  
         for (int j = 1; j < sz(ob[i]); j++) {  
            edges[ob[i][j - 1]].pb(ob[i][j]);  
            in[ob[i][j]]++;  
         }  
      }  
      queue<int> q;  
      for (int i = 0; i < n; i++) {  
         if (in[i] == 0) {  
            q.push(i);  
         }  
      }  
      if (!sz(q)) return false;  
      while (sz(q)) {  
         int cur = q.front();  
         q.pop();  
         for (int to: edges[cur]) {  
            in[to]--;  
            if (in[to] == 0) q.push(to);  
         }  
      }  
      for (int i = 0; i < n; i++) if (in[i]) return false;  
      return true;  
   };  
  
   vi ans;  
   auto generate_answer = [&](int limit) {  
      vvi edges(n);  
      vi in(n);  
      for (int i = 0; i < limit; i++) {  
         for (int j = 1; j < sz(ob[i]); j++) {  
            edges[ob[i][j - 1]].pb(ob[i][j]);  
            in[ob[i][j]]++;  
         }  
      }  
      priority_queue<int, vi, greater<>> pq;  
      for (int i = 0; i < n; i++) {  
         if (in[i] == 0) {  
            pq.push(i);  
         }  
      }  
      vi order;  
      while (sz(pq)) {  
         int cur = pq.top();  
         order.pb(cur);  
         pq.pop();  
         for (int to: edges[cur]) {  
            in[to]--;  
            if (in[to] == 0) pq.push(to);  
         }  
      }  
      ans = order;  
   };  
  
   while (l <= r) {  
      int mid = l + r >> 1;  
      if (chk(mid)) {  
         ret = mid, l = mid + 1;  
         generate_answer(mid);  
      } else r = mid - 1;  
   }  
   for (int i: ans) cout << i + 1 << ' ';  
}