Submission #237486

#	Time	Username	Problem	Language	Result	Execution time	Memory
237486		Fischer	Evacuation plan (IZhO18_plan)	C++14	100 / 100	816 ms	51096 KiB

plan

/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author Miguel Mini
 */

#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define trav(v, x) for (auto v : x)
#define re(x, y, z) for (int x=y; x<z; ++x)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define set_to(x, v) fill(all(x), v)
#define eb emplace_back
#define lso(x) ((x)&-(x))
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 10;
const int inf = 1e9 + 10;
vector<ii> g[maxn];
int c[maxn];
int dis[maxn];
int n, k;

void dijkstra() {
  fill(dis+1, dis+n+1, inf);
  priority_queue<ii, vector<ii>, greater<ii>> Q;
  re(i, 0, k) {
    Q.push({dis[c[i]] = 0, c[i]});
  }
  while (!Q.empty()) {
    auto q = Q.top(); Q.pop();
    int w = q.first;
    int v = q.second;
    if (w != dis[v]) continue;
    for (auto node : g[v]) {
      int temp = w + node.second;
      int u = node.first;
      if (temp < dis[u]) {
        dis[u] = temp;
        Q.push({dis[u], u});
      }
    }
  }
}

int rnk[maxn], link[maxn];
void make(int x) {
  link[x] = x;
  rnk[x] = 0;
}

int get(int x) {
  if (x == link[x]) return x;
  return link[x] = get(link[x]);
}

bool merge(int x, int y) {
  x = get(x); y = get(y);
  if (x == y) return 0;
  if (rnk[x] < rnk[y]) swap(x, y);
  rnk[x] += rnk[x] == rnk[y];
  link[y] = x;
}

vector<ii> T[maxn];
int h[maxn];
const int LOG = 18;
int st[maxn][LOG];
int min_edge[maxn][LOG];

void dfs(int x, int p=0, int e=0) {
  h[x] = p == 0 ? 0 : h[p] + 1;
  st[x][0] = p == 0 ? x : p;
  min_edge[x][0] = e;
  for (int k = 1; k < LOG; ++k) {
    st[x][k] = st[st[x][k-1]][k-1];
    min_edge[x][k] = min(min_edge[x][k-1], min_edge[st[x][k-1]][k-1]);
  }
  for (auto e : T[x]) {
    if (e.first == p) continue;
    dfs(e.first, x, e.second);
  }
}

int jump(int x, int l) {
  for (int k = 0; k < LOG; ++k) {
    if (l & (1<<k)) {
      x = st[x][k];
    }
  }
  return x;
}

int lca(int x, int y) {
  if (h[x] > h[y]) swap(x, y);
  y = jump(y, h[y] - h[x]);
  if (x == y) return x;
  for (int k = LOG-1; k >= 0; --k) {
    if (st[x][k] != st[y][k]) {
      x = st[x][k];
      y = st[y][k];
    }
  }
  return st[x][0];
}

int min_edge_jump(int x, int l) {
  int ans = inf;
  for (int k = LOG-1; k >= 0; --k) {
    if (l & (1<<k)) {
      ans = min(ans, min_edge[x][k]);
      x = st[x][k];
    }
  }
  return ans;
}

int get_min(int a, int b) {
  int c = lca(a, b);
  return min(min_edge_jump(a, h[a]-h[c]), min_edge_jump(b, h[b]-h[c]));
}

class IZHO_18_plan {
public:

    void solveOne(istream& in, ostream& out) {
      int m;
      in >> n >> m;
      vector<pair<ii, int>> edges;
      re(i, 0, m) {
        int a, b, w;
        in >> a >> b >> w;
        g[a].eb(b, w);
        g[b].eb(a, w);
        edges.push_back({{a, b}, 0});
      }
      in >> k;
      re(i, 0, k) in >> c[i];
      dijkstra();
      for (auto& e : edges) {
        e.second = min(dis[e.first.first], dis[e.first.second]);
      }
      sort(all(edges), [](pair<ii, int> p, pair<ii, int> q) {
        return p.second > q.second;
      });
      re(i, 1, n+1) make(i);
      for (auto e : edges) {
        if (merge(e.first.first, e.first.second)) {
          T[e.first.first].push_back({e.first.second, e.second});
          T[e.first.second].push_back({e.first.first, e.second});
        }
      }
      dfs(1);
      int q;
      in >> q;
      while (q--) {
        int a, b;
        in >> a >> b;
        out << get_min(a, b) << endl;
      }
    }

    void solve(istream& in, ostream& out) {
        int testNumber = 1;
        //in >> testNumber;
        re(tc, 1, testNumber+1) {
            //out << "Case #" << tc << ": ";
            solveOne(in, out);
        }
    }
};


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
	IZHO_18_plan solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}

Compilation message (stderr)

plan.cpp: In function 'bool merge(int, int)':
plan.cpp:67:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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