Submission #231233

#	Time	Username	Problem	Language	Result	Execution time	Memory
231233		xiaowuc1	Wild Boar (JOI18_wild_boar)	C++14	100 / 100	8996 ms	602340 KiB

wild_boar

#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <complex>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_set>
#include <vector>

using namespace std;

// BEGIN NO SAD
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define derr if(1) cerr
typedef vector<int> vi;
// END NO SAD

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

struct edge {
  int from, to, w, id;
  edge(){}
  edge(int a, int b, int c, int d) {
    from=a;
    to=b;
    w=c;
    id=d;
  }
};
struct path {
  int f, l;
  ll w;
  path(){clear();}
  path(int a, int b, ll c) {
    f = a;
    l = b;
    w = c;
  }
  void clear() {
    f = -1;
    w=1e18;
  }
  bool valid() {
    return f >= 0;
  }
  bool operator==(const path& p) {
    return f == p.f && l==p.l && w==p.w;
  }
};
const ll INF = 1e14;
vector<int> edges[2000];
edge alledges[4000];
ll dp[4000][4000];
vector<path> bestpaths[2000][2000];
int n, m;

void calculatebestpaths(vector<path>& paths) {
  vector<path> ret(4);
  for(path out: paths) {
    if(out.w < ret[0].w) ret[0] = out;
  }
  // ret[1] doesn't match either edge
  for(path out: paths) {
    if(out.f == ret[0].f) continue;
    if(out.l == ret[0].l) continue;
    if(out.w < ret[1].w) ret[1] = out;
  }
  // ret[2] doesn't match (a, b)
  for(path out: paths) {
    if(out.f == ret[0].f) continue;
    if(out.l == ret[1].l) continue;
    if(out.w < ret[2].w) ret[2] = out;
  }
  // ret[3] doesn't match (b, a)
  for(path out: paths) {
    if(out.l == ret[0].l) continue;
    if(out.f == ret[1].f) continue;
    if(out.w < ret[3].w) ret[3] = out;
  }
  for(int i = 0; i < sz(ret); i++) {
    if(!ret[i].valid()) ret.erase(ret.begin() + i--);
  }
  paths.swap(ret);
}

void merge(vector<path>& ret, const vector<path>& a, const vector<path>& b) {
  ret.clear();
  for(path lhs: a) {
    for(path rhs: b) {
      if(alledges[lhs.l].to != alledges[rhs.f].from) continue;
      if((lhs.l^rhs.f) == 1) continue;
      ret.push_back(path(lhs.f, rhs.l, lhs.w + rhs.w));
    }
  }
  calculatebestpaths(ret);
}

const int KOOSAGA_SZ = 1 << 17;
vector<path> koosagatree[2 * KOOSAGA_SZ];
int numloc;
void upd(int idx) {
  idx += KOOSAGA_SZ;
  // assumes already set
  while(idx > 1) {
    idx /= 2;
    merge(koosagatree[idx], koosagatree[2*idx], koosagatree[2*idx+1]);
  }
}
ll qry() {
  int lhs = KOOSAGA_SZ;
  int rhs = KOOSAGA_SZ + numloc - 2;
  deque<vector<path>> lq, rq;
  while(lhs <= rhs) {
    if(lhs == rhs) {
      lq.push_back(koosagatree[lhs]);
      break;
    }
    if(lhs%2) lq.push_back(koosagatree[lhs++]);
    if(rhs%2==0) rq.push_front(koosagatree[rhs--]);
    lhs /= 2;
    rhs /= 2;
  }
  while(sz(rq)) {
    lq.push_back(rq.front());
    rq.pop_front();
  }
  assert(sz(lq));
  while(sz(lq) > 1) {
    auto a = lq.front(); lq.pop_front();
    auto b = lq.front(); lq.pop_front();
    vector<path> c;
    merge(c, a, b);
    lq.push_front(c);
  }
  if(sz(lq[0]) == 0) return -1;
  return lq[0].front().w;
}

void dijkstra(int srcid) {
  dp[srcid][srcid] = alledges[srcid].w;
  typedef pair<ll, int> pli;
  priority_queue<pli> q;
  q.push({-dp[srcid][srcid], srcid});
  while(sz(q)) {
    ll ww;
    int edgeid;
    tie(ww, edgeid) = q.top(); q.pop();
    ww *= -1;
    if(dp[srcid][edgeid] != ww) continue;
    for(int outid: edges[alledges[edgeid].to]) {
      if((edgeid^outid) == 1) continue;
      if(dp[srcid][outid] > dp[srcid][edgeid] + alledges[outid].w) {
        dp[srcid][outid] = dp[srcid][edgeid] + alledges[outid].w;
        q.push({-dp[srcid][outid], outid});
      }
    }
  }
}

int locs[100000];
void solve() {
  memset(dp, 1, sizeof(dp));
  int t;
  cin >> n >> m >> t >> numloc;
  for(int i = 0; i < m; i++) {
    int a, b, w;
    cin >> a >> b >> w;
    a--; b--;
    alledges[2*i] = edge(a, b, w, 2*i);
    alledges[2*i+1] = edge(b, a, w, 2*i+1);
    edges[a].push_back(2*i);
    edges[b].push_back(2*i+1);
  }
  for(int i = 0; i < 2*m; i++) dijkstra(i);
  for(int i = 0; i < 2*m; i++) {
    int srcnode = alledges[i].from;
    for(int j = 0; j < 2*m; j++) {
      if(dp[i][j] > INF) continue;
      int destnode = alledges[j].to;
      bestpaths[srcnode][destnode].push_back(path(i, j, dp[i][j]));
    }
  }
  for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) {
    calculatebestpaths(bestpaths[i][j]);
  }
  for(int i = 0; i < numloc; i++) {
    cin >> locs[i];
    locs[i]--;
  }
  for(int i = 0; i + 1 < numloc; i++) {
    koosagatree[KOOSAGA_SZ + i] = bestpaths[locs[i]][locs[i+1]];
  }
  for(int x = KOOSAGA_SZ-1; x > 0; x--) {
    merge(koosagatree[x], koosagatree[2*x], koosagatree[2*x+1]);
  }
  while(t--) {
    int idx, val;
    cin >> idx >> val;
    locs[--idx] = --val;
    if(idx > 0) {
      koosagatree[KOOSAGA_SZ + idx - 1] = bestpaths[locs[idx-1]][locs[idx]];
      upd(idx-1);
    }
    if(idx + 1 < numloc) {
      koosagatree[KOOSAGA_SZ + idx] = bestpaths[locs[idx]][locs[idx+1]];
      upd(idx);
    }
    cout << qry() << "\n";
  }
}

// are there edge cases (N=1?)
// are array sizes proper (scaled by proper constant, for example 2* for koosaga tree)
// integer overflow?
// DS reset properly between test cases

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  solve();
}

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