Submission #1055710

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055710		juicy	Wild Boar (JOI18_wild_boar)	C++17	100 / 100	3808 ms	406156 KiB

wild_boar

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

using T = array<long long, 3>;

const int N = 2e3 + 5, K = 1e5 + 5;
const long long inf = 1e18;

int n, m, t, k;
int x[K];
array<T, 4> d[N][N], s[4 * K];
vector<array<int, 2>> g[N];

void opt(array<T, 4> &buc, vector<T> cands) {
  for (int i = 0; i < 4; ++i) {
    buc[i] = {inf, -1, -1};
  }
  for (auto p : cands) {
    buc[0] = min(buc[0], p);
  }
  for (auto p : cands) {
    if (p[1] != buc[0][1] && p[2] != buc[0][2]) {
      buc[1] = min(buc[1], p);
    }
  } 
  for (auto p : cands) {
    if (p[1] != buc[0][1] && p[2] != buc[1][2]) {
      buc[2] = min(buc[2], p);
    }
    if (p[1] != buc[1][1] && p[2] != buc[0][2]) {
      buc[3] = min(buc[3], p);
    }
  }
}

bool add(array<T, 4> &buc, T cands) {
  vector<T> nw;
  for (int i = 0; i < 4; ++i) {
    if (buc[i][0] != inf) {
      nw.push_back(buc[i]);
    }
  } 
  nw.push_back(cands);
  opt(buc, nw);
  for (auto x : buc) {
    if (x == cands) {
      return 1;
    }
  }
  return 0;
}

void dijkstra(int src, array<T, 4> *d) {
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < 4; ++j) {
      d[i][j] = {inf, -1, -1};
    }
  }
  using dat = array<long long, 4>;
  priority_queue<dat, vector<dat>, greater<dat>> pq;
  for (auto [j, c] : g[src]) {
    pq.push({c, j, j, src});
  }
  while (pq.size()) {
    auto [c, u, s, t] = pq.top(); pq.pop();
    if (!add(d[u], {c, s, t})) {
      continue;
    }
    for (auto [v, w] : g[u]) {
      if (v != t) {
        pq.push({c + w, v, s, u});
      }
    }
  }
}

void pul(int id) {
  vector<T> cands;
  for (int i = 0; i < 4; ++i) {
    for (int j = 0; j < 4; ++j) {
      if (s[id * 2][i][2] != s[id * 2 + 1][j][1]) {
        cands.push_back({s[id * 2][i][0] + s[id * 2 + 1][j][0], s[id * 2][i][1], s[id * 2 + 1][j][2]});
      }
    }
  }
  opt(s[id], cands);
  vector<T>().swap(cands);
}

void bld(int id = 1, int l = 1, int r = k - 1) {
  if (l == r) {
    int u = x[l], v = x[l + 1];
    opt(s[id], {d[u][v][0], d[u][v][1], d[u][v][2], d[u][v][3]});
    return;
  }
  int md = (l + r) / 2;
  bld(id * 2, l, md);
  bld(id * 2 + 1, md + 1, r);
  pul(id);
}

void upd(int i, int id = 1, int l = 1, int r = k - 1) {
  if (l == r) {
    int u = x[l], v = x[l + 1];
    opt(s[id], {d[u][v][0], d[u][v][1], d[u][v][2], d[u][v][3]});
    return;
  }
  int md = (l + r) / 2;
  if (i <= md) {
    upd(i, id * 2, l, md);
  } else {
    upd(i, id * 2 + 1, md + 1, r);
  }
  pul(id);
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> m >> t >> k;
  while (m--) {
    int a, b, c; cin >> a >> b >> c;
    g[a].push_back({b, c});
    g[b].push_back({a, c});
  }
  for (int i = 1; i <= n; ++i) {
    dijkstra(i, d[i]);
  }
  for (int i = 1; i <= k; ++i) {
    cin >> x[i];
  }
  bld();
  while (t--) {
    int p, q; cin >> p >> q;
    x[p] = q;
    if (p > 1) {
      upd(p - 1);
    }
    if (p < k) {
      upd(p);
    }
    cout << (s[1][0][0] == inf ? -1 : s[1][0][0]) << "\n";
  }
  return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 35 / 35
• Subtask 3: 15 / 15
• Subtask 4: 38 / 38