Submission #203567

#	Time	Username	Problem	Language	Result	Execution time	Memory
203567		EntityIT	Wild Boar (JOI18_wild_boar)	C++14	100 / 100	11598 ms	558660 KiB

wild_boar

#include<bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;

template<class T>
inline bool asMn(T &a, const T &b) { return a > b ? a = b, true : false; }
template<class T>
inline bool asMx(T &a, const T &b) { return a < b ? a = b, true : false; }

const LL infLL = 1e18;
mt19937 rng( (int)chrono::steady_clock::now().time_since_epoch().count() );

int n, nDay, nSta;

struct Edge {
  int from, to, w;
  Edge(int _from, int _to, int _w) : from(_from), to(_to), w(_w) {}
};
vector<Edge> edge;
vector<vector<int> > gr;

vector<vector<LL> > d;
void dijkstra(int s) {
  d[s][s] = edge[s].w;
  priority_queue<pair<LL, int> > pq;
  pq.emplace(-d[s][s], s);
  while (sz(pq) ) {
    LL curD = -pq.top().first; int u = pq.top().second; pq.pop();

    if (curD ^ d[s][u]) continue ;

    for (int v : gr[edge[u].to]) if ( (u >> 1) ^ (v >> 1) ) {
      if (asMn(d[s][v], curD + edge[v].w) ) pq.emplace(-d[s][v], v);
    }
  }
}

void optimize(vector<tuple<LL, int, int> > &a) {
  vector<tuple<LL, int, int> > nA;
  if (sz(a) ) nA.emplace_back(*min_element(all(a) ) );

  tuple<LL, int, int> mn{ infLL, -1, -1 };
  for (auto &i : a) if (get<1>(i) ^ get<1>(nA[0]) && get<2>(i) ^ get<2>(nA[0])) asMn(mn, i);
  nA.emplace_back(mn);

  mn = { infLL, -1, -1 };
  for (auto &i : a) if (get<1>(i) ^ get<1>(nA[0]) && get<2>(i) ^ get<2>(nA[1])) asMn(mn, i);
  nA.emplace_back(mn);

  mn = { infLL, -1, -1 };
  for (auto &i : a) if (get<1>(i) ^ get<1>(nA[1]) && get<2>(i) ^ get<2>(nA[0])) asMn(mn, i);
  nA.emplace_back(mn);

  auto tmp = find(all(nA), tuple<LL, int, int>{ infLL, -1, -1 });
  while (tmp != nA.end() ) {
    nA.erase(tmp);
    tmp = find(all(nA), tuple<LL, int, int>{ infLL, -1, -1 });
  }

  a.swap(nA);
}
vector<vector<vector<tuple<LL, int, int> > > > optimalE;
vector<int> x;
struct It {
  #define lC (i << 1)
  #define rC (i << 1 | 1)
  #define Mid ( (Left + Right) >> 1)
  #define rt int i = 1, int Left = 0, int Right = nSta - 2

  struct Node {
    vector<tuple<LL, int, int> > val;
    Node() { val.clear(); }

    Node operator + (const Node &_) const {
      Node ret;
      for (auto i : val) {
        for (auto j : _.val) if ( (get<2>(i) >> 1) ^ (get<1>(j) >> 1) ) {
          ret.val.emplace_back(get<0>(i) + get<0>(j), get<1>(i), get<2>(j) );
        }
      }
      optimize(ret.val);

      return ret;
    }
  };
  vector<Node> node;
  It(int nNode) { node.assign(nNode, Node() ); }

  void build(rt) {
    if (!(Left ^ Right) ) {
      node[i].val = optimalE[ x[Left] ][ x[Left + 1] ];
      return ;
    }
    build(lC, Left, Mid);
    build(rC, Mid + 1, Right);
    node[i] = node[lC] + node[rC];
  }

  void upd(int pos, rt) {
    if (Left == Right) {
      node[i].val = optimalE[ x[Left] ][ x[Left + 1] ];
      return ;
    }
    if (pos <= Mid) upd(pos, lC, Left, Mid);
    else upd(pos, rC, Mid + 1, Right);
    node[i] = node[lC] + node[rC];
  }
};

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  #ifdef FourLeafClover
  freopen("input", "r", stdin);
  #endif // FourLeafClover

  int m; cin >> n >> m >> nDay >> nSta;

  gr.assign(n, {} );
  while (m--) {
    int u, v, w; cin >> u >> v >> w; --u; --v;
    gr[u].emplace_back(sz(edge) ); edge.emplace_back(u, v, w);
    gr[v].emplace_back(sz(edge) ); edge.emplace_back(v, u, w);
  }

  d.assign(sz(edge), vector<LL>(sz(edge), infLL) );
  for (int s = 0; s < sz(edge); ++s) dijkstra(s);

  optimalE.assign(n, vector<vector<tuple<LL, int, int> > >(n) );
  for (int from = 0; from < n; ++from) {
    for (int to = 0; to < n; ++to) if (from ^ to) {
      for (int s : gr[from]) {
        for (int t : gr[to]) optimalE[from][to].emplace_back(d[s][t ^ 1], s, t ^ 1);
      }
      optimize(optimalE[from][to]);
    }
  }

  x.assign(nSta, 0);
  for (auto &i : x) cin >> i, --i;
  It it( (nSta + 5) << 2); it.build();

  while (nDay--) {
    int p, v; cin >> p >> v; --p; --v;
    x[p] = v;
    if (p) it.upd(p - 1);
    if (p + 1 < nSta) it.upd(p);

    tuple<LL, int, int> ans{ infLL, -1, -1 };
    for (auto _ : it.node[1].val) asMn(ans, _);
    cout << (get<0>(ans) ^ infLL ? get<0>(ans) : -1) << '\n';
  }

  return 0;
}

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