Submission #62647

#	Time	Username	Problem	Language	Result	Execution time	Memory
62647		gusfring	Wild Boar (JOI18_wild_boar)	C++14	62 / 100	6120 ms	665300 KiB

wild_boar

#include <bits/stdc++.h>
 
using namespace std;
 
 
#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]; 

 
void Min(ll& a, ll b) { a = min(a, b); }
 
void ComputeDist(ll n, ll m) {
  priority_queue<pair<ll, ll>> pq;
  vector<ll> inc_count(n);
  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]) {
        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);
  }
}
 
void Solve(ll) {
  ll n, m, t, l;
  scanf("%lld %lld %lld %lld", &n, &m, &t, &l);
  assert(t == 1);
  head.resize(n, -1);
  VEVE(e, 0, m) {
    ll a, b, c;
    scanf("%lld %lld %lld", &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) {
    scanf("%d", &s);
    --s;
  }
  vector<ll> dp_cur(m), dp_pred(m);
  VEVE(_, 0, t) {
    ll p, q;
    scanf("%lld %lld", &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);
          }
        }
      }
      swap(dp_pred, dp_cur);
    }
    ll res = *min_element(ALL(dp_pred));
    if (res >= INF / 2)
      res = -1;
    printf("%lld\n", res);
  }
}
 
 
int main() {
  ll tests = 1;
  VEVE(test, 1, tests + 1) Solve(test);
  return 0;
}

Compilation message (stderr)

wild_boar.cpp: In function 'void Solve(ll)':
wild_boar.cpp:81:19: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
     scanf("%d", &s);
                 ~~^
wild_boar.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld %lld %lld", &n, &m, &t, &l);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld %lld", &a, &b, &c);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:81:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &s);
     ~~~~~^~~~~~~~~~
wild_boar.cpp:87:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld", &p, &q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~

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