Submission #221472

#	Time	Username	Problem	Language	Result	Execution time	Memory
221472		rama_pang	Wild Boar (JOI18_wild_boar)	C++14	100 / 100	11017 ms	593012 KiB

wild_boar

#include <bits/stdc++.h>
using namespace std;
using lint = long long;

const int MAXN = 2005;
const int MAXM = 4005;
const int MAXL = 100005;
const lint INF = 1e18;

struct edge_t {
  int u, v, w; // u = from, v = to, w = weight
  edge_t() {}
  edge_t(int u, int v, int w) : u(u), v(v), w(w) {}
};

int N, M, T, L;

namespace Graph {

vector<edge_t> edges;
vector<int> adj[MAXN];

lint EdgeEdgeDistance[MAXM][MAXM]; // EdgeEdgeDistance[X][Y][Type] = Shortest Path from X.u to Y.v, where we use X and Y

lint Distance[MAXN][MAXN][7]; // Distance[A][B][Type] = Shortest Path between Vertices A and B
int FirstEdge[MAXN][MAXN][7]; // FirstEdge[A][B][Type] = first edge in the shortest path from A to B (adjacent to A)
int LastEdge[MAXN][MAXN][7]; // LastEdge[A][B][Type] = last edge in the shortest path from A to B (adjacent to B)

// Distance Types:
// 1 The overall shortest distance, which uses (X, Y)
// 2 The overall shortest distance without X and Y
// 3 The overall shortest distance without X, which uses (U, V)
// 4 The overall shortest distance without X and V
// 5 The overall shortest distance without Y, which uses (S, E)
// 6 The overall shortest distance without S and Y

void Read() {
  M *= 2;
  for (int i = 0; i < (M / 2); i++) {
    int A, B, C;
    cin >> A >> B >> C;
    A--, B--;

    adj[A].emplace_back(edges.size());
    edges.emplace_back(A, B, C);

    adj[B].emplace_back(edges.size());
    edges.emplace_back(B, A, C);
  }
}

void Dijkstra(int X) { // Finds all EdgeEdgeDistance[X][]
  priority_queue<pair<lint, int>, vector<pair<lint, int>>, greater<pair<lint, int>>> pq;
  pq.emplace(edges[X].w, X);
  EdgeEdgeDistance[X][X] = edges[X].w; // from edges[X].u to edges[X].v

  // Run Dijkstra to find EdgeEdgeDistance[X][]
  // Make sure we do not do a U-turn

  while (!pq.empty()) {
    int cur = pq.top().second;
    lint cur_dist = pq.top().first; 
    pq.pop();

    if (cur_dist != EdgeEdgeDistance[X][cur]) continue;
    int u = edges[cur].v;

    for (auto nxt : adj[u]) {
      if (cur == (nxt ^ 1)) continue; // We cannot U-turn back
      lint &nxt_dist = EdgeEdgeDistance[X][nxt];

      if (nxt_dist == -1 || nxt_dist > cur_dist + edges[nxt].w) {
        nxt_dist = cur_dist + edges[nxt].w;
        pq.emplace(nxt_dist, nxt);
      }
    }
  }
}

void AllPairsShortestPath() { // Compute everything involving Shortest Paths
  // Compute EdgeEdgeDistance[][]
  memset(EdgeEdgeDistance, -1, sizeof(EdgeEdgeDistance));
  for (int X = 0; X < M; X++) Dijkstra(X);

  // Compute Distance, FirstEdge, and LastEdge
  memset(Distance, -1, sizeof(Distance));
  memset(FirstEdge, -1, sizeof(FirstEdge));
  memset(LastEdge, -1, sizeof(LastEdge));

  // Compute Distance[][][1] = The overall shortest distance, which uses (X, Y)
  for (int X = 0; X < M; X++) {
    for (int Y = 0; Y < M; Y++) {
      if (EdgeEdgeDistance[X][Y] == -1) continue;
      int A = edges[X].u;
      int B = edges[Y].v;
      if (Distance[A][B][1] == -1 || Distance[A][B][1] > EdgeEdgeDistance[X][Y]) {
        Distance[A][B][1] = EdgeEdgeDistance[X][Y];
        FirstEdge[A][B][1] = X;
        LastEdge[A][B][1] = Y;
      }
    }
  }

  // Compute Distance[][][2] = The overall shortest distance without X and Y
  for (int I = 0; I < M; I++) {
    for (int J = 0; J < M; J++) {
      int A = edges[I].u;
      int B = edges[J].v;
      int X = FirstEdge[A][B][1];
      int Y = LastEdge[A][B][1];
      if (I == X || J == Y) continue;
      if (EdgeEdgeDistance[I][J] == -1) continue;
      if (Distance[A][B][2] == -1 || Distance[A][B][2] > EdgeEdgeDistance[I][J]) {
        Distance[A][B][2] = EdgeEdgeDistance[I][J]; 
        FirstEdge[A][B][2] = I;
        LastEdge[A][B][2] = J;
      }
    }
  }

  // Compute Distance[][][3] = The overall shortest distance without X, which uses (U, V)
  for (int U = 0; U < M; U++) {
    for (int V = 0; V < M; V++) {
      if (EdgeEdgeDistance[U][V] == -1) continue;
      int A = edges[U].u;
      int B = edges[V].v;
      int X = FirstEdge[A][B][1];
      if (U == X) continue;

      if (Distance[A][B][3] == -1 || Distance[A][B][3] > EdgeEdgeDistance[U][V]) {
        Distance[A][B][3] = EdgeEdgeDistance[U][V];
        FirstEdge[A][B][3] = U;
        LastEdge[A][B][3] = V;
      }
    }
  }

  // Compute Distance[][][4] = The overall shortest distance without X and V
  for (int I = 0; I < M; I++) {
    for (int J = 0; J < M; J++) {
      if (EdgeEdgeDistance[I][J] == -1) continue;
      int A = edges[I].u;
      int B = edges[J].v;
      int X = FirstEdge[A][B][1];
      int V = LastEdge[A][B][3];
      if (I == X || J == V) continue;

      if (Distance[A][B][4] == -1 || Distance[A][B][4] > EdgeEdgeDistance[I][J]) {
        Distance[A][B][4] = EdgeEdgeDistance[I][J];
        FirstEdge[A][B][4] = I;
        LastEdge[A][B][4] = J;
      }
    }
  }

  // Compute Distance[][][5] = The overall shortest distance without Y, which uses (S, E)
  for (int S = 0; S < M; S++) {
    for (int E = 0; E < M; E++) {
      if (EdgeEdgeDistance[S][E] == -1) continue;
      int A = edges[S].u;
      int B = edges[E].v;
      int Y = LastEdge[A][B][1];
      if (E == Y) continue;

      if (Distance[A][B][5] == -1 || Distance[A][B][5] > EdgeEdgeDistance[S][E]) {
        Distance[A][B][5] = EdgeEdgeDistance[S][E];
        FirstEdge[A][B][5] = S;
        LastEdge[A][B][5] = E;
      }
    }
  }

  // Compute Distance[][][6] = The overall shortest distance without S and Y
  for (int I = 0; I < M; I++) {
    for (int J = 0; J < M; J++) {
      if (EdgeEdgeDistance[I][J] == -1) continue;
      int A = edges[I].u;
      int B = edges[J].v;
      int S = FirstEdge[A][B][5];
      int Y = LastEdge[A][B][1];
      if (I == S || J == Y) continue;
      if (Distance[A][B][6] == -1 || Distance[A][B][6] > EdgeEdgeDistance[I][J]) {
        Distance[A][B][6] = EdgeEdgeDistance[I][J]; 
        FirstEdge[A][B][6] = I;
        LastEdge[A][B][6] = J;
      }
    }
  }
}

}

class SegmentTree {
 
 private:

  struct Data {
    array<lint, 7> dp; // dp[Type] = Answer for supply run on current segment
    array<int, 7> first_edge;
    array<int, 7> last_edge; 

    lint& operator [] (int i) { return dp[i]; }
    const lint& operator [] (int i) const { return dp[i]; }

    Data() {
      for (int i = 0; i <= 6; i++) {
        dp[i] = -1;
        first_edge[i] = -1;
        last_edge[i] = -1;
      }
    }

    Data(int u, int v) {
      for (int i = 1; i <= 6; i++) {
        dp[i] = Graph::Distance[u][v][i];
        first_edge[i] = Graph::FirstEdge[u][v][i];
        last_edge[i] = Graph::LastEdge[u][v][i];
      }
      for (int i = 1; i <= 6; i++) {
        if (dp[i] < 0) dp[i] = INF;
      }
    }

    Data(Data A, Data B) {
      if (A[1] == -1) { *this = B; return; }
      if (B[1] == -1) { *this = A; return; }
      for (int i = 1; i <= 6; i++) dp[i] = INF;
      
      // Type 1 The overall shortest distance, which uses (X, Y)
      for (int P = 1; P <= 6; P++) {
        for (int Q = 1; Q <= 6; Q++) {
          if (A.last_edge[P] == (B.first_edge[Q] ^ 1)) continue; // cannot make U-turns
          if (dp[1] > A[P] + B[Q]) {
            dp[1] = A[P] + B[Q];
            first_edge[1] = A.first_edge[P];
            last_edge[1] = B.last_edge[Q];
          }
        }
      }

      // Type 2 The overall shortest distance without X and Y
      for (int P = 1; P <= 6; P++) {
        for (int Q = 1; Q <= 6; Q++) {
          if (A.last_edge[P] == (B.first_edge[Q] ^ 1)) continue; // cannot make U-turns
          if (first_edge[1] == A.first_edge[P]) continue;
          if (last_edge[1] == B.last_edge[Q]) continue;
          if (dp[2] > A[P] + B[Q]) {
            dp[2] = A[P] + B[Q];
            first_edge[2] = A.first_edge[P];
            last_edge[2] = B.last_edge[Q];
          }
        }
      }
      
      // Type 3 The overall shortest distance without X, which uses (U, V)
      for (int P = 1; P <= 6; P++) {
        for (int Q = 1; Q <= 6; Q++) {
          if (A.last_edge[P] == (B.first_edge[Q] ^ 1)) continue; // cannot make U-turns
          if (first_edge[1] == A.first_edge[P]) continue;
          if (dp[3] > A[P] + B[Q]) {
            dp[3] = A[P] + B[Q];
            first_edge[3] = A.first_edge[P];
            last_edge[3] = B.last_edge[Q];
          }
        }
      }      

      // Type 4 The overall shortest distance without X and V
      for (int P = 1; P <= 6; P++) {
        for (int Q = 1; Q <= 6; Q++) {
          if (A.last_edge[P] == (B.first_edge[Q] ^ 1)) continue; // cannot make U-turns
          if (first_edge[1] == A.first_edge[P]) continue;
          if (last_edge[3] == B.last_edge[Q]) continue;
          if (dp[4] > A[P] + B[Q]) {
            dp[4] = A[P] + B[Q];
            first_edge[4] = A.first_edge[P];
            last_edge[4] = B.last_edge[Q];
          }
        }
      }      

      // Type 5 The overall shortest distance without Y, which uses (S, E)
      for (int P = 1; P <= 6; P++) {
        for (int Q = 1; Q <= 6; Q++) {
          if (A.last_edge[P] == (B.first_edge[Q] ^ 1)) continue; // cannot make U-turns
          if (last_edge[1] == B.last_edge[Q]) continue;
          if (dp[5] > A[P] + B[Q]) {
            dp[5] = A[P] + B[Q];
            first_edge[5] = A.first_edge[P];
            last_edge[5] = B.last_edge[Q];
          }
        }
      }      

      // Type 6 The overall shortest distance without S and Y
      for (int P = 1; P <= 6; P++) {
        for (int Q = 1; Q <= 6; Q++) {
          if (A.last_edge[P] == (B.first_edge[Q] ^ 1)) continue; // cannot make U-turns
          if (first_edge[5] == A.first_edge[P]) continue;
          if (last_edge[1] == B.last_edge[Q]) continue;
          if (dp[6] > A[P] + B[Q]) {
            dp[6] = A[P] + B[Q];
            first_edge[6] = A.first_edge[P];
            last_edge[6] = B.last_edge[Q];
          }
        }
      }      
    }
  };

  int sz;
  vector<Data> Tree;
  vector<int> X; // Supply Plan

  void Update(int pos, int u, int v) {
    Tree[pos += sz] = Data(u, v);
    for (pos /= 2; pos > 0; pos /= 2) {
      Tree[pos] = Data(Tree[pos * 2], Tree[pos * 2 + 1]);
    }
  }

  Data Query(int L, int R) {
    Data left, right;
    for (L += sz, R += sz; L < R; L /= 2, R /= 2) {
      if (L & 1) left = Data(left, Tree[L++]);
      if (R & 1) right = Data(Tree[--R], right);
    }
    return Data(left, right);
  }

 public:

  SegmentTree(vector<int> X) : X(X) {
    sz = (int) X.size() - 1;
    Tree.resize(2 * sz);

    for (int i = 0; i < sz; i++) {
      Tree[i + sz] = Data(X[i], X[i + 1]);
    }
    for (int i = sz - 1; i > 0; i--) {
      Tree[i] = Data(Tree[i * 2], Tree[i * 2 + 1]);
    }
  }

  void Update(int P, int Q) {
    X[P] = Q;
    if (P > 0) Update(P - 1, X[P - 1], X[P]);
    if (P < sz) Update(P, X[P], X[P + 1]);
  }

  lint Query() {
    lint res = Query(0, sz).dp[1];
    if (res == INF) res = -1;
    return res;
  }
};

void Solve() {
  vector<int> X(L);
  for (int i = 0; i < L; i++) {
    cin >> X[i];
    X[i]--;
  }

  SegmentTree Solver(X);
  for (int i = 0; i < T; i++) {
    int P, Q;
    cin >> P >> Q;
    Solver.Update(--P, --Q);
    cout << Solver.Query() << "\n";
  }
}

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

  cin >> N >> M >> T >> L;

  Graph::Read();
  Graph::AllPairsShortestPath();

  Solve();

  return 0;
}

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