Submission #201023

#	Time	Username	Problem	Language	Result	Execution time	Memory
201023		quocnguyen1012	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1375 ms	49924 KiB

plan

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;

const int maxn = 1e5 + 5, maxm = 5e5 + 5;

class DSU
{
  vector<int> lab;
public:
  void init(int n)
  {
    lab.assign(n + 5, -1);
  }
  int finds(int u)
  {
    if (lab[u] < 0) return u;
    return lab[u] = finds(lab[u]);
  }
  bool same(int u, int v)
  {
    return finds(u) == finds(v);
  }
  bool merges(int u, int v)
  {
    u = finds(u); v = finds(v);
    if (u == v) return false;
    if (lab[v] < lab[u]) swap(u, v);
    lab[u] += lab[v];
    lab[v] = u;
    return true;
  }
}dsu;

class edge_list
{
public:
  int u, v, w;
  bool operator < (const edge_list & other) const
  {
    return w > other.w;
  }
}edge[maxm];
int N, M, K, Q;
int dist[maxn];
vector<pair<int, int>> Tree[maxn];
vector<int> adj[maxn];
int par[maxn][20], rmq[maxn][20], depth[maxn];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

void dfs(int u, int p = -1)
{
  for (int i = 1; (1 << i) <= N; ++i){
    par[u][i] = par[par[u][i - 1]][i - 1];
    rmq[u][i] = min(rmq[u][i - 1], rmq[par[u][i - 1]][i - 1]);
  }
  for (auto v : Tree[u]){
    if (v.fi == p) continue;
    depth[v.fi] = depth[u] + 1;
    par[v.fi][0] = u;
    rmq[v.fi][0] = v.se;
    dfs(v.fi, u);
  }
}

int LCA(int x, int y)
{
  if (depth[x] < depth[y]) swap(x, y);
  for (int k = 19; k >= 0; --k){
    if (depth[par[x][k]] >= depth[y]){
      x = par[x][k];
    }
  }
  if (x == y) return x;
  for (int k = 19; k >= 0; --k){
    if (par[x][k] != par[y][k]){
      x = par[x][k];
      y = par[y][k];
    }
  }
  return par[x][0];
}

int up(int x, int p)
{
  int res = 1e9;
  for (int k = 19; k >= 0; --k){
    if (depth[par[x][k]] >= depth[p]){
      res = min(res, rmq[x][k]);
      x = par[x][k];
    }
  }
  return res;
}

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  if (fopen("A.INP", "r")){
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  }
  cin >> N >> M;
  for (int i = 1; i <= M; ++i){
    cin >> edge[i].u >> edge[i].v >> edge[i].w;
    adj[edge[i].u].pb(i); adj[edge[i].v].pb(i);
  }
  fill_n(&dist[0], maxn, 1e9 + 5);
  cin >> K;
  for (int i = 1; i <= K; ++i){
    int x; cin >> x;
    dist[x] = 0;
    pq.push(mp(0, x));
  }
  while (pq.size()){
    auto now = pq.top(); pq.pop();
    if (now.fi != dist[now.se]) continue;
    for (int i : adj[now.se]){
      int v = edge[i].u + edge[i].v - now.se;
      if (dist[v] > now.fi + edge[i].w){
        dist[v] = now.fi + edge[i].w;
        pq.push(mp(dist[v], v));
      }
    }
  }
  for (int i = 1; i <= M; ++i){
    edge[i].w = min(dist[edge[i].u], dist[edge[i].v]);
  }
  sort(edge + 1, edge + 1 + M);
  dsu.init(N);
  for (int i = 1; i <= M; ++i){
    if (dsu.merges(edge[i].u, edge[i].v)){
      Tree[edge[i].u].pb(mp(edge[i].v, edge[i].w));
      Tree[edge[i].v].pb(mp(edge[i].u, edge[i].w));
      ///cerr << edge[i].u << ' ' << edge[i].v << ' ' << edge[i].w << '\n';
    }
  }
  for (int i = 1; i <= N; ++i){
    if (depth[i] == 0){
      depth[i] = 1;
      dfs(i);
    }
  }
  cin >> Q;
  while (Q--){
    int u, v; cin >> u >> v;
    assert(dsu.same(u, v));
    int lc = LCA(u, v);
    cout << min(up(u, lc), up(v, lc)) << '\n';
  }
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:106:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.INP", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
plan.cpp:107:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.OUT", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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