제출 #1134930

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1134930		JelalTkm	Evacuation plan (IZhO18_plan)	C++20	100 / 100	402 ms	46008 KiB

plan

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

using namespace std;

#define int long long int

const int N = 1e5 + 10;
const int md = 1e9 + 7;
const int INF = 1e10;

vector<int> dist(N, INF);
vector<vector<pair<int, int>>> qu(N, vector<pair<int, int>> ());
vector<int> ans(N);

class DisjointSets {
 
  private:
  vector<int> p;
  vector<vector<int>> d;
  vector<int> dst;
  
  public:
    DisjointSets(int n) : p(n + 1), dst(n + 1), d(n + 1) {
      for (int i = 0; i <= n; i++) { p[i] = i, dst[i] = dist[i]; d[i] = {i};}
    }
 
  int get(int u) {
    return p[u] = (u == p[u] ? u : get(p[u]));
  }
 
  void unite(int u, int v) {
    u = get(u);
    v = get(v);
    if (u == v) {
      return;
    }
    if ((int) d[u].size() < (int) d[v].size())
      swap(u, v);
    dst[u] = min(dst[u], dst[v]);
    d[u].insert(d[u].end(), d[v].begin(), d[v].end());
    for (auto i : d[v]) {
      p[i] = u;
      for (auto [j, num] : qu[i])
        if (p[num] == u) ans[j] = max(ans[j], dst[u]);
    }
    return;
  }
 
};

int32_t main(int32_t argc, char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  int T = 1;
  // cin >> T;
  while (T--) {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> g(n + 1, vector<pair<int, int>> ());
    for (int i = 0; i < m; i++) {
      int u, v, w;
      cin >> u >> v >> w;
      g[u].push_back(make_pair(v, w));
      g[v].push_back(make_pair(u, w));
    }

    int k;
    cin >> k;
    set<pair<int, int>> q;
    for (int i = 0; i < k; i++) {
      int u;
      cin >> u;
      dist[u] = 0;
      q.insert({0, u});
    }

    vector<bool> visited(n + 1);

    while (!q.empty()) {
      int v = (*q.begin()).second;
      q.erase(q.begin());
      if (!visited[v])
        for (auto i : g[v]) {
          dist[i.first] = min(dist[i.first], dist[v] + i.second);
          if (!visited[i.first])
            q.insert({dist[i.first], i.first});
        }
      visited[v] = 1;
    }

    // for (int i = 1; i <= n; i++)
    //   cout << i << " " << dist[i] << '\n';

    int que;
    cin >> que;

    for (int i = 0; i < que; i++) {
      int u, v;
      cin >> u >> v;
      qu[u].push_back(make_pair(i, v));
      qu[v].push_back(make_pair(i, u));
    }

    vector<pair<int, int>> dst;
    for (int i = 1; i <= n; i++)
      dst.push_back(make_pair(dist[i], i));

    sort(dst.rbegin(), dst.rend());

    DisjointSets dsu(n + 1);

    int ind = 0;
    vector<bool> vis(n + 1);
    while (ind < (int) dst.size()) {
      auto [ds, u] = dst[ind];
      vis[u] = 1;
      // cout << u << " " << dsu.distance(u) << '\n';
      for (auto i : g[u]) {
        if (vis[i.first]) {
          dsu.unite(i.first, u);
        }
      }
      ind++;
    }

    for (int i = 0; i < que; i++)
      cout << ans[i] << '\n';
  }

  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 46 / 46