Submission #721115

#	Time	Username	Problem	Language	Result	Execution time	Memory
721115		cig32	Evacuation plan (IZhO18_plan)	C++17	100 / 100	618 ms	175548 KiB

plan

#include "bits/stdc++.h"
#define int long long
using namespace std;
const int MAXN = 1e5 + 10;
int n, m, k, q;
priority_queue<pair<int,int>, vector<pair<int,int> >,greater<pair<int,int> > >pq;
vector<pair<int,int> > adj[MAXN];
pair<int,int> w[MAXN];
int dist[MAXN];
bool vis[MAXN];
int dsu[MAXN];
int set_of(int u) {
  if(dsu[u] == u) return u;
  return dsu[u] = set_of(dsu[u]);
}
void union_(int u, int v) {
  dsu[set_of(u)] = set_of(v);
}
int rept[MAXN]; // representative node of set
vector<int> krt[2*MAXN]; // actual krt
int ans[2*MAXN];
int nxt; // next node
int dep[2*MAXN];
vector<int> e;
void dfs(int node, int prv) {
  dep[node] = (prv == -1 ? 0 : dep[prv] + 1);
  e.push_back(node);
  for(int x: krt[node]) {
    if(x != prv) {
      dfs(x, node);
      e.push_back(node);
    }
  }
}
int l[2*MAXN], r[2*MAXN];
pair<int,int> st[19][4*MAXN];
int lca(int x, int y) {
  int m1 = min(l[x], l[y]);
  int m2 = max(r[x], r[y]);
  int k = 32- __builtin_clz(m2-m1+1) -1;
  return min(st[k][m1],st[k][m2-(1<<k)+1]).second;
}
void solve(int tc) {
  cin >> n >> m;
  nxt = n+1;
  for(int i=0; i<m; i++) {
    int a, b, w;
    cin >> a >> b >> w;
    adj[a].push_back({b, w});
    adj[b].push_back({a, w});
  }
  for(int i=1; i<=n; i++) {
    dist[i] = 1e18;
  }
  cin >> k;
  for(int i=0; i<k; i++) {
    int x;
    cin >> x;
    dist[x] = 0;
    pq.push({0, x});
  }
  while(pq.size()) {
    pair<int,int> t= pq.top();
    pq.pop();
    if(!vis[t.second]) {
      vis[t.second]=1;
      for(pair<int,int> x:adj[t.second]) {
        if(!vis[x.first] && dist[x.first]>dist[t.second]+x.second) {
          dist[x.first]=dist[t.second]+x.second;
          pq.push({dist[x.first],x.first});
        }
      }
    }
  }
  for(int i=1; i<=n; i++) w[i] = {dist[i], i};
  sort(w+1, w+1+n);
  reverse(w+1, w+1+n);
  for(int i=1; i<=n; i++) {
    vis[i] = 0;
    rept[i] = i;
    ans[i] = dist[i];
    dsu[i] = i;
  }
  for(int i=1; i<=n; i++) {
    int node = w[i].second;
    int weight = w[i].first;
    vis[node] = 1;
    for(pair<int, int> x: adj[node]) {
      if(vis[x.first]) {
        if(set_of(x.first) != set_of(node)) {
          int to = x.first;
          int r1 = rept[set_of(to)];
          int r2 = rept[set_of(node)];
          krt[nxt].push_back(r1);
          krt[nxt].push_back(r2);
          ans[nxt] = min(ans[r1], ans[r2]);
          union_(to, node);
          rept[set_of(node)] = nxt;
          nxt++;
        }
      }
    }
  }
  int rt = nxt - 1;
  dfs(rt, -1);
  for(int i=0; i<e.size(); i++) r[e[i]] = i;
  for(int i=e.size()-1; i>=0; i--) l[e[i]] = i;
  for(int i=0; i<e.size(); i++) st[0][i] = {dep[e[i]], e[i]};
  for(int i=1; i<19; i++) {
    for(int j=0; j+(1<<i)-1<e.size(); j++) {
      st[i][j] = min(st[i-1][j], st[i-1][j+(1<<(i-1))]);
    }
  }
  cin >> q;
  while(q--) {
    int s, t;
    cin >> s >> t;
    cout << ans[lca(s, t)] << "\n";
  }
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t=1;
  //cin>>t;
  for(int i=1; i<=t; i++)solve(i);
}

Compilation message (stderr)

plan.cpp: In function 'void solve(long long int)':
plan.cpp:86:9: warning: unused variable 'weight' [-Wunused-variable]
   86 |     int weight = w[i].first;
      |         ^~~~~~
plan.cpp:106:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |   for(int i=0; i<e.size(); i++) r[e[i]] = i;
      |                ~^~~~~~~~~
plan.cpp:108:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |   for(int i=0; i<e.size(); i++) st[0][i] = {dep[e[i]], e[i]};
      |                ~^~~~~~~~~
plan.cpp:110:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for(int j=0; j+(1<<i)-1<e.size(); j++) {
      |                  ~~~~~~~~~~^~~~~~~~~

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