답안 #221419

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
221419	2020-04-10T02:51:50 Z	rama_pang	Wild Boar (JOI18_wild_boar)	C++14	47 / 100	14097 ms	409460 KB

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 ShortestPath {

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

// Distance[X][Y][Use Y?] = Shortest Path from edges[X].u to edges[Y].v given we must use X and we must use/not use Y
lint Distance[MAXM][MAXM][2];
int LastEdgeDistance[MAXM][MAXM][2]; // last edge used in Distance[][][]

// ShortestPathEdge[X][edges[Y].v] = Y that has the shortest distance given that we have to use edge X to reach edges[Y].v
int ShortestPathEdge[MAXM][MAXN]; 

void Read() {
  M = 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 Distance[X][][1][1]
  priority_queue<pair<lint, int>, vector<pair<lint, int>>, greater<pair<lint, int>>> pq;
  pq.emplace(edges[X].w, X);
  Distance[X][X][1] = edges[X].w; // from edges[X].u to edges[X].v

  // Run Dijkstra to find Distance[X][][1][1].
  // 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 != Distance[X][cur][1]) continue;
    int u = edges[cur].v;

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

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

void Solve() { // Computes Distance[][][][] and ShortestPathEdge[][][]
  memset(Distance, -1, sizeof(Distance));
  memset(LastEdgeDistance, -1, sizeof(LastEdgeDistance));
  memset(ShortestPathEdge, -1, sizeof(ShortestPathEdge));

  // Computes Distance[][][1] and ShortestPathEdge[][]
  for (int X = 0; X < M; X++) {
    Dijkstra(X);
    for (int Y = 0; Y < M; Y++) {
      if (Distance[X][Y][1] == -1) continue;
      LastEdgeDistance[X][Y][1] = Y;
      int V = edges[Y].v;
      int &SPE = ShortestPathEdge[X][V];
      if (SPE == -1 || Distance[X][SPE][1] > Distance[X][Y][1]) {
        SPE = Y;
      }
    }
  }

  // Computes Distance[][][0]
  for (int X = 0; X < M; X++) {
    vector<multiset<pair<lint, int>>> VertexDist(N);
    for (int Y = 0; Y < M; Y++) {
      VertexDist[edges[Y].v].emplace(Distance[X][Y][1], LastEdgeDistance[X][Y][1]);
    }
    for (int Y = 0; Y < M; Y++) {
      auto it = VertexDist[edges[Y].v].find({Distance[X][Y][1], LastEdgeDistance[X][Y][1]});
      VertexDist[edges[Y].v].erase(it);
      if (!VertexDist[edges[Y].v].empty()) {
        Distance[X][Y][0] = begin(VertexDist[edges[Y].v])->first;
        LastEdgeDistance[X][Y][0] = begin(VertexDist[edges[Y].v])->second;
      }
      VertexDist[edges[Y].v].emplace(Distance[X][Y][1], LastEdgeDistance[X][Y][1]);
    }
  }
}

}

namespace DynamicProgramming {

int X[MAXL];

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

  // T = 1
  int P, Q;
  cin >> P >> Q;
  X[--P] = --Q;
}

long long Solve() {
  vector<long long> dp(M, INF), next_dp(M, INF);

  // Special Case for pos = 0
  for (auto i : ShortestPath::adj[X[0]]) {
    for (int j = 0; j < M; j++) {
      if (ShortestPath::edges[j].v == X[1] && ShortestPath::Distance[i][j][1] != -1) {
        dp[j] = min(dp[j], ShortestPath::Distance[i][j][1]);
      }
    }
  }

  for (int pos = 1; pos < L - 1; pos++) {
    for (int last_edge = 0; last_edge < M; last_edge++) {
      if (ShortestPath::edges[last_edge].v != X[pos]) continue;

      int nxt_edge = ShortestPath::ShortestPathEdge[last_edge][X[pos + 1]];
      if (nxt_edge == -1) continue;

      next_dp[nxt_edge] = min(next_dp[nxt_edge], 
        dp[last_edge] + ShortestPath::Distance[last_edge][nxt_edge][1] - ShortestPath::edges[last_edge].w);
      
      int exclude_nxt_edge = ShortestPath::LastEdgeDistance[last_edge][nxt_edge][0];
      if (exclude_nxt_edge == -1) continue;
      next_dp[exclude_nxt_edge] = min(next_dp[exclude_nxt_edge], 
        dp[last_edge] + ShortestPath::Distance[last_edge][exclude_nxt_edge][1] - ShortestPath::edges[last_edge].w);
    }

    dp = next_dp;
    next_dp.assign(M, INF);
  }

  long long res = *min_element(begin(dp), end(dp));
  if (res == INF) res = -1;
  return res;
}

}

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

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

  ShortestPath::Read();
  ShortestPath::Solve();
  
  DynamicProgramming::Read();
  cout << DynamicProgramming::Solve() << "\n";

  return 0;
}

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	212 ms	408444 KB	Output is correct
2	Correct	211 ms	408656 KB	Output is correct
3	Correct	223 ms	408508 KB	Output is correct
4	Correct	207 ms	408440 KB	Output is correct
5	Correct	216 ms	408568 KB	Output is correct
6	Correct	225 ms	408440 KB	Output is correct
7	Correct	207 ms	408440 KB	Output is correct
8	Correct	211 ms	408648 KB	Output is correct
9	Correct	213 ms	408440 KB	Output is correct
10	Correct	215 ms	408440 KB	Output is correct
11	Correct	212 ms	408592 KB	Output is correct
12	Correct	211 ms	408440 KB	Output is correct
13	Correct	210 ms	408440 KB	Output is correct
14	Correct	214 ms	408568 KB	Output is correct
15	Correct	213 ms	408440 KB	Output is correct
16	Correct	205 ms	408440 KB	Output is correct
17	Correct	209 ms	408492 KB	Output is correct
18	Correct	208 ms	408444 KB	Output is correct
19	Correct	208 ms	408440 KB	Output is correct
20	Correct	213 ms	408572 KB	Output is correct
21	Correct	211 ms	408440 KB	Output is correct
22	Correct	210 ms	408440 KB	Output is correct
23	Correct	218 ms	408572 KB	Output is correct
24	Correct	225 ms	408440 KB	Output is correct
25	Correct	210 ms	408440 KB	Output is correct

Subtask #2
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	212 ms	408444 KB	Output is correct
2	Correct	211 ms	408656 KB	Output is correct
3	Correct	223 ms	408508 KB	Output is correct
4	Correct	207 ms	408440 KB	Output is correct
5	Correct	216 ms	408568 KB	Output is correct
6	Correct	225 ms	408440 KB	Output is correct
7	Correct	207 ms	408440 KB	Output is correct
8	Correct	211 ms	408648 KB	Output is correct
9	Correct	213 ms	408440 KB	Output is correct
10	Correct	215 ms	408440 KB	Output is correct
11	Correct	212 ms	408592 KB	Output is correct
12	Correct	211 ms	408440 KB	Output is correct
13	Correct	210 ms	408440 KB	Output is correct
14	Correct	214 ms	408568 KB	Output is correct
15	Correct	213 ms	408440 KB	Output is correct
16	Correct	205 ms	408440 KB	Output is correct
17	Correct	209 ms	408492 KB	Output is correct
18	Correct	208 ms	408444 KB	Output is correct
19	Correct	208 ms	408440 KB	Output is correct
20	Correct	213 ms	408572 KB	Output is correct
21	Correct	211 ms	408440 KB	Output is correct
22	Correct	210 ms	408440 KB	Output is correct
23	Correct	218 ms	408572 KB	Output is correct
24	Correct	225 ms	408440 KB	Output is correct
25	Correct	210 ms	408440 KB	Output is correct
26	Correct	222 ms	408612 KB	Output is correct
27	Correct	275 ms	408944 KB	Output is correct
28	Correct	275 ms	408828 KB	Output is correct
29	Correct	533 ms	408952 KB	Output is correct
30	Correct	545 ms	409080 KB	Output is correct
31	Correct	621 ms	408952 KB	Output is correct
32	Correct	642 ms	408952 KB	Output is correct
33	Correct	494 ms	408952 KB	Output is correct
34	Correct	535 ms	409076 KB	Output is correct
35	Correct	644 ms	408952 KB	Output is correct
36	Correct	580 ms	408952 KB	Output is correct
37	Correct	524 ms	409080 KB	Output is correct
38	Correct	492 ms	408932 KB	Output is correct
39	Correct	518 ms	408952 KB	Output is correct
40	Correct	483 ms	408952 KB	Output is correct
41	Correct	495 ms	408952 KB	Output is correct
42	Correct	507 ms	409080 KB	Output is correct
43	Correct	476 ms	408952 KB	Output is correct
44	Correct	486 ms	409232 KB	Output is correct
45	Correct	425 ms	408952 KB	Output is correct

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	212 ms	408444 KB	Output is correct
2	Correct	211 ms	408656 KB	Output is correct
3	Correct	223 ms	408508 KB	Output is correct
4	Correct	207 ms	408440 KB	Output is correct
5	Correct	216 ms	408568 KB	Output is correct
6	Correct	225 ms	408440 KB	Output is correct
7	Correct	207 ms	408440 KB	Output is correct
8	Correct	211 ms	408648 KB	Output is correct
9	Correct	213 ms	408440 KB	Output is correct
10	Correct	215 ms	408440 KB	Output is correct
11	Correct	212 ms	408592 KB	Output is correct
12	Correct	211 ms	408440 KB	Output is correct
13	Correct	210 ms	408440 KB	Output is correct
14	Correct	214 ms	408568 KB	Output is correct
15	Correct	213 ms	408440 KB	Output is correct
16	Correct	205 ms	408440 KB	Output is correct
17	Correct	209 ms	408492 KB	Output is correct
18	Correct	208 ms	408444 KB	Output is correct
19	Correct	208 ms	408440 KB	Output is correct
20	Correct	213 ms	408572 KB	Output is correct
21	Correct	211 ms	408440 KB	Output is correct
22	Correct	210 ms	408440 KB	Output is correct
23	Correct	218 ms	408572 KB	Output is correct
24	Correct	225 ms	408440 KB	Output is correct
25	Correct	210 ms	408440 KB	Output is correct
26	Correct	222 ms	408612 KB	Output is correct
27	Correct	275 ms	408944 KB	Output is correct
28	Correct	275 ms	408828 KB	Output is correct
29	Correct	533 ms	408952 KB	Output is correct
30	Correct	545 ms	409080 KB	Output is correct
31	Correct	621 ms	408952 KB	Output is correct
32	Correct	642 ms	408952 KB	Output is correct
33	Correct	494 ms	408952 KB	Output is correct
34	Correct	535 ms	409076 KB	Output is correct
35	Correct	644 ms	408952 KB	Output is correct
36	Correct	580 ms	408952 KB	Output is correct
37	Correct	524 ms	409080 KB	Output is correct
38	Correct	492 ms	408932 KB	Output is correct
39	Correct	518 ms	408952 KB	Output is correct
40	Correct	483 ms	408952 KB	Output is correct
41	Correct	495 ms	408952 KB	Output is correct
42	Correct	507 ms	409080 KB	Output is correct
43	Correct	476 ms	408952 KB	Output is correct
44	Correct	486 ms	409232 KB	Output is correct
45	Correct	425 ms	408952 KB	Output is correct
46	Correct	578 ms	408568 KB	Output is correct
47	Incorrect	14097 ms	409460 KB	Output isn't correct
48	Halted	0 ms	0 KB	-

Subtask #4
0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Correct	212 ms	408444 KB	Output is correct
2	Correct	211 ms	408656 KB	Output is correct
3	Correct	223 ms	408508 KB	Output is correct
4	Correct	207 ms	408440 KB	Output is correct
5	Correct	216 ms	408568 KB	Output is correct
6	Correct	225 ms	408440 KB	Output is correct
7	Correct	207 ms	408440 KB	Output is correct
8	Correct	211 ms	408648 KB	Output is correct
9	Correct	213 ms	408440 KB	Output is correct
10	Correct	215 ms	408440 KB	Output is correct
11	Correct	212 ms	408592 KB	Output is correct
12	Correct	211 ms	408440 KB	Output is correct
13	Correct	210 ms	408440 KB	Output is correct
14	Correct	214 ms	408568 KB	Output is correct
15	Correct	213 ms	408440 KB	Output is correct
16	Correct	205 ms	408440 KB	Output is correct
17	Correct	209 ms	408492 KB	Output is correct
18	Correct	208 ms	408444 KB	Output is correct
19	Correct	208 ms	408440 KB	Output is correct
20	Correct	213 ms	408572 KB	Output is correct
21	Correct	211 ms	408440 KB	Output is correct
22	Correct	210 ms	408440 KB	Output is correct
23	Correct	218 ms	408572 KB	Output is correct
24	Correct	225 ms	408440 KB	Output is correct
25	Correct	210 ms	408440 KB	Output is correct
26	Correct	222 ms	408612 KB	Output is correct
27	Correct	275 ms	408944 KB	Output is correct
28	Correct	275 ms	408828 KB	Output is correct
29	Correct	533 ms	408952 KB	Output is correct
30	Correct	545 ms	409080 KB	Output is correct
31	Correct	621 ms	408952 KB	Output is correct
32	Correct	642 ms	408952 KB	Output is correct
33	Correct	494 ms	408952 KB	Output is correct
34	Correct	535 ms	409076 KB	Output is correct
35	Correct	644 ms	408952 KB	Output is correct
36	Correct	580 ms	408952 KB	Output is correct
37	Correct	524 ms	409080 KB	Output is correct
38	Correct	492 ms	408932 KB	Output is correct
39	Correct	518 ms	408952 KB	Output is correct
40	Correct	483 ms	408952 KB	Output is correct
41	Correct	495 ms	408952 KB	Output is correct
42	Correct	507 ms	409080 KB	Output is correct
43	Correct	476 ms	408952 KB	Output is correct
44	Correct	486 ms	409232 KB	Output is correct
45	Correct	425 ms	408952 KB	Output is correct
46	Correct	578 ms	408568 KB	Output is correct
47	Incorrect	14097 ms	409460 KB	Output isn't correct
48	Halted	0 ms	0 KB	-

답안 #221419

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 35.0 / 35.0

Subtask #3 0 / 15.0

Subtask #4 0 / 38.0

Subtask #1
12.0 / 12.0

Subtask #2
35.0 / 35.0

Subtask #3
0 / 15.0

Subtask #4
0 / 38.0