oj.uz

Submission #882875

# Submission time Handle Problem Language Result Execution time Memory
882875 2023-12-04T00:01:06 Z MilosMilutinovic Wild Boar (JOI18_wild_boar) C++14
62 / 100
 4065 ms 956188 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m, t, l;
  cin >> n >> m >> t >> l;
  vector<vector<pair<int, int>>> g(n);
  for (int i = 0; i < m; i++) {
    int x, y, z;
    cin >> x >> y >> z;
    --x; --y;
    g[x].emplace_back(y, z);
    g[y].emplace_back(x, z);
  }
  vector<int> seq(l);
  for (int i = 0; i < l; i++) {
    cin >> seq[i];
    --seq[i];
  }
  {
    int p, x;
    cin >> p >> x;
    --p; --x;
    seq[p] = x;
  }
  vector<int> deg(n);
  for (int i = 0; i < n; i++) {
    deg[i] = (int) g[i].size();
  }
  vector<vector<int>> idx(n, vector<int>(n));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < deg[i]; j++) {
      idx[i][g[i][j].first] = j;
    }
  }
  const long long inf = (long long) 1e18;
  vector<vector<vector<vector<long long>>>> dist(n, vector<vector<vector<long long>>>(n));
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (i == j) {
        continue;
      }
      dist[i][j].resize(deg[i]);
      for (int k = 0; k < deg[i]; k++) {
        dist[i][j][k] = vector<long long>(deg[j], inf);
      }
    }
  }
  vector<vector<long long>> d(n);
  for (int i = 0; i < n; i++) {
    d[i].resize(deg[i]);
  }
  vector<int> ia(n), ib(n);
  set<tuple<long long, int, int>> st;
  for (int ver = 0; ver < n; ver++) {
    for (int e = 0; e < deg[ver]; e++) {
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < deg[i]; j++) {
          d[i][j] = inf;
        }
        ia[i] = -1;
        ib[i] = -1;
      }
      int to = g[ver][e].first;
      int w = g[ver][e].second;
      d[to][idx[to][ver]] = w;
      st.clear();
      st.emplace(d[to][idx[to][ver]], to, idx[to][ver]);
      ia[to] = idx[to][ver];
      auto Update = [&](int x, int y, long long z) {
        if (ia[x] == y || ib[x] == y) {
          st.erase(st.find({d[x][y], x, y}));
        }
        d[x][y] = z;
        if (ia[x] == y) {
          return;
        }
        if (ib[x] == y) {
          if (d[x][y] < d[x][ia[x]]) {
            swap(ia[x], ib[x]);
          }
          return;
        }
        if (ia[x] == -1) {
          ia[x] = y;
          st.emplace(d[x][y], x, y);
          return;
        }
        if (ib[x] == -1) {
          if (d[x][y] < d[x][ia[x]]) {
            swap(ia[x], ib[x]);
            ia[x] = y;
          } else {
            ib[x] = y;
          }
          st.emplace(d[x][y], x, y);
          return;
        }
        if (d[x][y] >= d[x][ia[x]] && d[x][y] < d[x][ib[x]]) {
          st.erase(st.find({d[x][ib[x]], x, ib[x]}));
          ib[x] = y;
          st.emplace(d[x][y], x, y);
          return;
        }
        if (d[x][y] < d[x][ia[x]]) {
          st.erase(st.find({d[x][ib[x]], x, ib[x]}));
          swap(ia[x], ib[x]);
          ia[x] = y;
          st.emplace(d[x][y], x, y);
        }
      };
      while (!st.empty()) {
        auto it = st.begin();
        int v = get<1>(*it);
        int lst = get<2>(*it);
        st.erase(it);
        for (int i = 0; i < deg[v]; i++) {
          if (i == lst) {
            continue;
          }
          int to = g[v][i].first;
          int w = g[v][i].second;
          if (d[to][idx[to][v]] > d[v][lst] + w) {
            Update(to, idx[to][v], d[v][lst] + w);
            assert((int) st.size() <= 2 * n);
          }
        }
      }
      for (int i = ver + 1; i < n; i++) {
        if (i == ver) {
          continue;
        }
        for (int j = 0; j < deg[i]; j++) {
          dist[ver][i][e][j] = d[i][j];
        }
      }
    }
  }
  vector<vector<vector<vector<int>>>> good(n, vector<vector<vector<int>>>(n));
  for (int from = 0; from < n; from++) {
    for (int to = 0; to < n; to++) {
      if (from == to) {
        continue;
      }
      good[from][to].resize(deg[from]);
      for (int i = 0; i < deg[from]; i++) {
        if (from < to) {
          int x = -1, y = -1;
          for (int j = 0; j < deg[to]; j++) {
            if (x == -1 || dist[from][to][i][j] < dist[from][to][i][x]) {
              y = x;
              x = j; 
            } else if (y == -1 || dist[from][to][i][j] < dist[from][to][i][y]) {
              y = j;
            }
          }  
          if (x != -1) {
            good[from][to][i].push_back(x);
          }
          if (y != -1) {
            good[from][to][i].push_back(y);
          }
        } else {
          int x = -1, y = -1;
          for (int j = 0; j < deg[to]; j++) {
            if (x == -1 || dist[to][from][j][i] < dist[to][from][x][i]) {
              y = x;
              x = j; 
            } else if (y == -1 || dist[to][from][j][i] < dist[to][from][y][i]) {
              y = j;
            }
          }  
          if (x != -1) {
            good[from][to][i].push_back(x);
          }
          if (y != -1) {
            good[from][to][i].push_back(y);
          }
        }
      }
    }
  }
  vector<long long> dp(n, inf);
  for (int i = 0; i < deg[seq[0]]; i++) {
    for (int j = 0; j < deg[seq[1]]; j++) {
      if (seq[0] <= seq[1]) {
        dp[j] = min(dp[j], dist[seq[0]][seq[1]][i][j]);
      } else {
        dp[j] = min(dp[j], dist[seq[1]][seq[0]][j][i]);
      }
    }
  }
  vector<long long> new_dp(n);
  vector<long long> val(n);
  for (int p = 2; p < l; p++) {
    for (int i = 0; i < deg[seq[p]]; i++) {
      new_dp[i] = inf;
    }
    for (int i = 0; i < deg[seq[p - 1]]; i++) {
      val[i] = inf;
    }
    {
      long long mn = inf;
      for (int i = 0; i < deg[seq[p - 1]]; i++) {
        val[i] = min(val[i], mn);
        mn = min(mn, dp[i]);
      }  
    }
    {
      long long mn = inf;
      for (int i = deg[seq[p - 1]] - 1; i >= 0; i--) {
        val[i] = min(val[i], mn);
        mn = min(mn, dp[i]);
      }
    }
    for (int i = 0; i < deg[seq[p - 1]]; i++) {
      if (val[i] != inf) {
        for (int j : good[seq[p - 1]][seq[p]][i]) {
          if (seq[p - 1] <= seq[p]) {
            new_dp[j] = min(new_dp[j], val[i] + dist[seq[p - 1]][seq[p]][i][j]);
          } else {
            new_dp[j] = min(new_dp[j], val[i] + dist[seq[p]][seq[p - 1]][j][i]);
          }
        }
      }
    }
    for (int i = 0; i < deg[seq[p]]; i++) {
      dp[i] = new_dp[i];
    }
  }
  long long res = inf;
  for (int i = 0; i < deg[seq.back()]; i++) {
    res = min(res, dp[i]);
  }
  cout << (res == inf ? -1 : res) << '\n';
  return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 600 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 600 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 11 ms 3164 KB Output is correct
28 Correct 11 ms 3172 KB Output is correct
29 Correct 59 ms 7252 KB Output is correct
30 Correct 76 ms 7548 KB Output is correct
31 Correct 118 ms 7260 KB Output is correct
32 Correct 116 ms 7552 KB Output is correct
33 Correct 71 ms 10092 KB Output is correct
34 Correct 76 ms 10492 KB Output is correct
35 Correct 132 ms 10672 KB Output is correct
36 Correct 104 ms 10700 KB Output is correct
37 Correct 66 ms 10208 KB Output is correct
38 Correct 75 ms 13648 KB Output is correct
39 Correct 97 ms 14148 KB Output is correct
40 Correct 77 ms 13792 KB Output is correct
41 Correct 88 ms 13672 KB Output is correct
42 Correct 100 ms 16208 KB Output is correct
43 Correct 89 ms 17408 KB Output is correct
44 Correct 92 ms 17492 KB Output is correct
45 Correct 62 ms 22096 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 600 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 11 ms 3164 KB Output is correct
28 Correct 11 ms 3172 KB Output is correct
29 Correct 59 ms 7252 KB Output is correct
30 Correct 76 ms 7548 KB Output is correct
31 Correct 118 ms 7260 KB Output is correct
32 Correct 116 ms 7552 KB Output is correct
33 Correct 71 ms 10092 KB Output is correct
34 Correct 76 ms 10492 KB Output is correct
35 Correct 132 ms 10672 KB Output is correct
36 Correct 104 ms 10700 KB Output is correct
37 Correct 66 ms 10208 KB Output is correct
38 Correct 75 ms 13648 KB Output is correct
39 Correct 97 ms 14148 KB Output is correct
40 Correct 77 ms 13792 KB Output is correct
41 Correct 88 ms 13672 KB Output is correct
42 Correct 100 ms 16208 KB Output is correct
43 Correct 89 ms 17408 KB Output is correct
44 Correct 92 ms 17492 KB Output is correct
45 Correct 62 ms 22096 KB Output is correct
46 Correct 136 ms 21540 KB Output is correct
47 Correct 2163 ms 236472 KB Output is correct
48 Correct 2574 ms 355176 KB Output is correct
49 Correct 2706 ms 440080 KB Output is correct
50 Correct 2807 ms 439652 KB Output is correct
51 Correct 2828 ms 438336 KB Output is correct
52 Correct 2798 ms 421976 KB Output is correct
53 Correct 2803 ms 421204 KB Output is correct
54 Correct 2835 ms 422780 KB Output is correct
55 Correct 2842 ms 421324 KB Output is correct
56 Correct 2948 ms 465272 KB Output is correct
57 Correct 3124 ms 511280 KB Output is correct
58 Correct 3310 ms 558784 KB Output is correct
59 Correct 3440 ms 607368 KB Output is correct
60 Correct 3678 ms 658312 KB Output is correct
61 Correct 3798 ms 712704 KB Output is correct
62 Correct 3964 ms 770052 KB Output is correct
63 Correct 4065 ms 828788 KB Output is correct
64 Correct 2480 ms 956188 KB Output is correct
65 Correct 2411 ms 955880 KB Output is correct

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 600 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 11 ms 3164 KB Output is correct
28 Correct 11 ms 3172 KB Output is correct
29 Correct 59 ms 7252 KB Output is correct
30 Correct 76 ms 7548 KB Output is correct
31 Correct 118 ms 7260 KB Output is correct
32 Correct 116 ms 7552 KB Output is correct
33 Correct 71 ms 10092 KB Output is correct
34 Correct 76 ms 10492 KB Output is correct
35 Correct 132 ms 10672 KB Output is correct
36 Correct 104 ms 10700 KB Output is correct
37 Correct 66 ms 10208 KB Output is correct
38 Correct 75 ms 13648 KB Output is correct
39 Correct 97 ms 14148 KB Output is correct
40 Correct 77 ms 13792 KB Output is correct
41 Correct 88 ms 13672 KB Output is correct
42 Correct 100 ms 16208 KB Output is correct
43 Correct 89 ms 17408 KB Output is correct
44 Correct 92 ms 17492 KB Output is correct
45 Correct 62 ms 22096 KB Output is correct
46 Correct 136 ms 21540 KB Output is correct
47 Correct 2163 ms 236472 KB Output is correct
48 Correct 2574 ms 355176 KB Output is correct
49 Correct 2706 ms 440080 KB Output is correct
50 Correct 2807 ms 439652 KB Output is correct
51 Correct 2828 ms 438336 KB Output is correct
52 Correct 2798 ms 421976 KB Output is correct
53 Correct 2803 ms 421204 KB Output is correct
54 Correct 2835 ms 422780 KB Output is correct
55 Correct 2842 ms 421324 KB Output is correct
56 Correct 2948 ms 465272 KB Output is correct
57 Correct 3124 ms 511280 KB Output is correct
58 Correct 3310 ms 558784 KB Output is correct
59 Correct 3440 ms 607368 KB Output is correct
60 Correct 3678 ms 658312 KB Output is correct
61 Correct 3798 ms 712704 KB Output is correct
62 Correct 3964 ms 770052 KB Output is correct
63 Correct 4065 ms 828788 KB Output is correct
64 Correct 2480 ms 956188 KB Output is correct
65 Correct 2411 ms 955880 KB Output is correct
66 Incorrect 14 ms 1016 KB Output isn't correct
67 Halted 0 ms 0 KB -