Submission #43983

#	Time	Username	Problem	Language	Result	Execution time	Memory
43983		azneye	Wild Boar (JOI18_wild_boar)	C++17	62 / 100	4683 ms	654880 KiB

wild_boar

#include <bits/stdc++.h>

using namespace std;

namespace {

#define VEVE(i, a, b) for (ll i = a, __##i = b; i < __##i; ++i)
#define RARA(i, a, b) for (ll i = a, __##i = b; i > __##i; --i)
#define VERA(x, seq) for (auto &x : seq)
#define SIZE(x) ((ll)(x.size()))
#define ALL(x) x.begin(), x.end()

typedef long long ll;
typedef double dd;
const ll MAX_EDGES = 4004;
const ll INF = 1LL << 60;
vector<ll> to, pred, head, cost;
vector<vector<ll>> rev_adj;
ll dist[MAX_EDGES][MAX_EDGES];
vector<pair<ll, ll>> best_edges[MAX_EDGES][MAX_EDGES / 2]; // edge -> vertex -> (inc edge, dist)
// top 2 shortest distance from edge to vertex

void Min(ll& a, ll b) { a = min(a, b); }

void ComputeDist(ll n, ll m) {
  priority_queue<pair<ll, ll>> pq; // (-dist, edge)
  vector<ll> inc_count(n); // # of edges incident to vertex i processed
  auto calc = [&](ll src_edge) {
    fill(ALL(inc_count), 0);
    dist[src_edge][src_edge] = 0;
    pq.emplace(0, src_edge);
    while (not pq.empty()) {
      const auto cur_dist = -pq.top().first;
      const auto edge = pq.top().second;
      pq.pop();
      if (cur_dist > dist[src_edge][edge])
        continue;
      if (++inc_count[to[edge]] > 2)
        continue;
      best_edges[src_edge][to[edge]].emplace_back(edge, cur_dist);
      for (ll nx_edge = head[to[edge]]; ~nx_edge; nx_edge = pred[nx_edge]) {
        // going back on same edge
        if ((edge ^ nx_edge) == 1)
          continue;
        if (cur_dist + cost[nx_edge] < dist[src_edge][nx_edge]) {
          dist[src_edge][nx_edge] = cur_dist + cost[nx_edge];
          pq.emplace(-dist[src_edge][nx_edge], nx_edge);
        }
      }
    }
  };
  memset(dist, 0x3F, sizeof(dist));
  VEVE(e, 0, m) {
    calc(e);
  }
//  PlnArr(dist, m, m);
}

void Solve(ll) {
  ll n, m, t, l;
  cin >> n >> m >> t >> l;
  assert(t == 1);
  head.resize(n, -1);
//  rev_adj.resize(n);
  VEVE(e, 0, m) {
    ll a, b, c;
    cin >> a >> b >> c;
    --a, --b;
    to.push_back(b);
    cost.push_back(c);
    pred.push_back(head[a]);
    head[a] = SIZE(pred) - 1;
//    rev_adj[b].push_back(head[a]);

    to.push_back(a);
    cost.push_back(c);
    pred.push_back(head[b]);
    head[b] = SIZE(pred) - 1;
//    rev_adj[a].push_back(head[b]);
  }
  m *= 2;
  ComputeDist(n, m);
  vector<ll> supply(l);
  VERA(s, supply) {
    cin >> s;
    --s;
  }
  vector<ll> dp_cur(m), dp_pred(m);
  VEVE(_, 0, t) {
    ll p, q;
    cin >> p >> q;
    --p, --q;
    supply[p] = q;
    fill(ALL(dp_pred), INF);
    for (ll e = head[supply.front()]; ~e; e = pred[e]) {
      dp_pred[e] = cost[e];
    }
    VEVE(i, 1, SIZE(supply)) {
      fill(ALL(dp_cur), INF);
      VEVE(pe, 0, m) {
        if (dp_pred[pe] < INF) {
          VERA(best, best_edges[pe][supply[i]]) {
            Min(dp_cur[best.first], dp_pred[pe] + best.second);
          }
        }
      }
//      DEBUG(dp_cur);
      swap(dp_pred, dp_cur);
    }
    ll res = *min_element(ALL(dp_pred));
    if (res >= INF / 2)
      res = -1;
    cout << res << '\n';
  }
}

void Init() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
}
}

int main() {
#ifdef AZN
  freopen("input.txt", "r", stdin);
#endif
  Init();
  ll tests = 1;
  VEVE(test, 1, tests + 1) Solve(test);
  return 0;
}

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