Submission #203560

#	Time	Username	Problem	Language	Result	Execution time	Memory
203560		EntityIT	Wild Boar (JOI18_wild_boar)	C++14	62 / 100	18074 ms	452472 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);
    }
  }
}

vector<vector<vector<pair<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 {
    map<pair<int, int>, LL> val;
    Node() { val.clear(); }

    Node operator + (const Node &_) const {
      Node ret;
      for (auto i : val) {
        for (auto j : _.val) if ( (i.first.second >> 1) ^ (j.first.first >> 1) ) {
          if (ret.val.count(make_pair(i.first.first, j.first.second) ) ) asMn(ret.val[make_pair(i.first.first, j.first.second)], i.second + j.second);
          else ret.val[make_pair(i.first.first, j.first.second)] = i.second + j.second;
        }
      }

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

  void build(rt) {
    if (!(Left ^ Right) ) {
      for (auto _ : optimalE[ x[Left] ][ x[Left + 1] ]) if (_ != make_pair(-1, -1) ) node[i].val[_] = d[_.first][_.second];
//      cerr << "Left:" << Left << " Right:" << Right << '\n';
//      for (auto _ : node[i].val) cerr << _.first.first << ' ' << _.first.second << ' ' << _.second << '\n';
      return ;
    }
    build(lC, Left, Mid);
    build(rC, Mid + 1, Right);
    node[i] = node[lC] + node[rC];
//    cerr << "Left:" << Left << " Right:" << Right << '\n';
//    for (auto _ : node[i].val) cerr << _.first.first << ' ' << _.first.second << ' ' << _.second << '\n';
  }

  void upd(int pos, rt) {
    if (Left == Right) {
      node[i].val.clear();
      for (auto _ : optimalE[ x[Left] ][ x[Left + 1] ]) if (_ != make_pair(-1, -1) ) node[i].val[_] = d[_.first][_.second];
      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<pair<int, int> > >(n) );
  for (int from = 0; from < n; ++from) {
    for (int to = 0; to < n; ++to) if (from ^ to) {
      optimalE[from][to].emplace_back(-1, -1);
      LL mn = infLL;
      for (int s : gr[from]) {
        for (int t : gr[to]) if (asMn(mn, d[s][t ^ 1]) ) optimalE[from][to].back() = { s, t ^ 1 };
      }

      optimalE[from][to].emplace_back(-1, -1);
      mn = infLL;
      for (int s : gr[from]) if (s ^ optimalE[from][to][0].first) {
        for (int t : gr[to]) if (t ^ 1 ^ optimalE[from][to][0].second && asMn(mn, d[s][t ^ 1]) ) optimalE[from][to].back() = { s, t ^ 1 };
      }

      optimalE[from][to].emplace_back(-1, -1);
      mn = infLL;
      for (int s : gr[from]) if (s ^ optimalE[from][to][0].first) {
        for (int t : gr[to]) if (t ^ 1 ^ optimalE[from][to][1].second && asMn(mn, d[s][t ^ 1]) ) optimalE[from][to].back() = { s, t ^ 1 };
      }

      optimalE[from][to].emplace_back(-1, -1);
      mn = infLL;
      for (int s : gr[from]) if (s ^ optimalE[from][to][1].first) {
        for (int t : gr[to]) if (t ^ 1 ^ optimalE[from][to][0].second && asMn(mn, d[s][t ^ 1]) ) optimalE[from][to].back() = { s, t ^ 1 };
      }

//      for (int s : gr[from]) {
//        for (int t : gr[to]) optimalE[from][to].emplace_back(s, t ^ 1);
//      }
    }
  }

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

//  LL ans = infLL;
//  for (auto _ : it.node[1].val) asMn(ans, _.second);
//  cerr << (ans ^ infLL ? ans : -1) << '\n';

  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);

    LL ans = infLL;
    for (auto _ : it.node[1].val) asMn(ans, _.second);
    cout << (ans ^ infLL ? ans : -1) << '\n';
  }

  return 0;
}

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