BOJ 28354 - 링크 컷 토마토

BOJ 28354 - 링크 컷 토마토

다익스타라 문제인데 아주 잘 구현해야한다.

각 간선이 언제 생기고 끊기는지를 map 같은걸로 시간복잡도가 널널하므로 잘 기록해둔다음에 현재 시간 $t$ 이후에 $i \to j$ 로 넘어갈 수 있는 시간이 언젠지를 $O(\log^2 M)$ 정도에 구해줄 수 있다면 충분하다.

본인은 map을 떡칠해서 걍 풀었는데 어차피 시간내에 돌아갈거란 믿음이 있었고 1000ms 밖에 안걸렸다.

const int inf = 1e9;
void solve() {
   int n, m, k, q;
   cin >> n >> m >> k >> q;
   map<int, map<int, vi>> in, out;
   vvi edges(n);
   for (int i = 0, u, v; i < m; i++) {
      cin >> u >> v, u--, v--;
      edges[u].pb(v), edges[v].pb(u);
      in[min(u, v)][max(u, v)].pb(0);
   }
   vi ans(n, inf);
   priority_queue<pi, vector<pi>, greater<>> pq;
   for (int i = 0, u; i < k; i++) {
      cin >> u, u--;
      ans[u] = 0;
      pq.push({0, u});
   }
   vector<array<int, 3>> qry(q);
   for (auto &[t, u, v]: qry) {
      cin >> t >> u >> v, u--, v--;
      edges[u].pb(v), edges[v].pb(u);
   }
   sort(all(qry));
   auto is_in = [&](int t, int u, int v) -> bool {
      if (!sz(in[u][v])) return 1;
      if (!sz(out[u][v])) return 0;
      if (in[u][v].back() > out[u][v].back()) return 0;
      return 1;
   };
   for (auto &[t, u, v]: qry) {
      if (u > v) swap(u, v);
      if (is_in(t, u, v)) in[u][v].pb(t);
      else out[u][v].pb(t);
   }
   auto nxt_t = [&](int t, int u, int v) -> int {
      if (u > v) swap(u, v);
      if (!sz(in[u][v])) return inf;
      int in_i = ubi(in[u][v], t);

      if (in_i == 0) return in[u][v][0] + 1;

      in_i--;
      int out_i = ubi(out[u][v], in[u][v][in_i]);
      if (out_i == sz(out[u][v])) return t + 1;
      if (out[u][v][out_i] >= t + 1) return t + 1;

      in_i++;
      if (sz(in[u][v]) == in_i) return inf;
      return in[u][v][in_i] + 1;
   };
   while (sz(pq)) {
      auto [cur_d, cur] = pq.top();
      pq.pop();
      if (ans[cur] ^ cur_d) continue;
      for (int to: edges[cur]) {
         if (ans[to] > cur_d + 1) {
            int nxt = nxt_t(cur_d, cur, to);
            if (nxt == inf) continue;

            if (ans[to] > nxt) {
               pq.push({ans[to] = nxt, to});
            }
         }
      }
   }
   for (int i = 0; i < n; i++) {
      cout << (ans[i] == inf ? -1 : ans[i]) << ' ';
   }
}