Submission #383076

#	Time	Username	Problem	Language	Result	Execution time	Memory
383076		Hegdahl	Relay Marathon (NOI20_relaymarathon)	C++17	17 / 100	6072 ms	515912 KiB

RelayMarathon

#pragma GCC optimize("Ofast")
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#ifdef ENABLE_DEBUG
#include <debug.h>
#else
#define DEBUG(...) do {} while (0)
#endif

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ull = unsigned long long;
using lll = __int128;
using ulll = unsigned __int128;

using ld = long double;

template<typename T, size_t N> using ar = array<T, N>;

template<typename T, typename Cmp = less<T>>
using iset = tree<T, null_type, Cmp, rb_tree_tag,
		  tree_order_statistics_node_update, allocator<T>>;

#define REPSI(name, start, stop, step) for (ll name = start; name < (ll)stop; name += step)
#define REPS(name, start, stop) REPSI(name, start, stop, 1)
#define REP(name, stop) REPS(name, 0, stop)

#define RREPSI(name, start, stop, step) for (ll name = stop-1; name >= (ll)start; name -= step)
#define RREPS(name, start, stop) RREPSI(name, start, stop, 1)
#define RREP(name, stop) RREPS(name, 0, stop)

template<typename T> void cins(T &first) { cin >> first; }
template<typename T, typename... Ts> void cins(T &first, T &second, Ts&... rest) {
  cin >> first;
  cins(second, rest...);
}

#define GET(type, ...) type __VA_ARGS__; cins(__VA_ARGS__)
#define GETI(...) GET(int, __VA_ARGS__)
#define GETLL(...) GET(ll, __VA_ARGS__)
#define GETS(...) GET(string, __VA_ARGS__)
#define GETD(...) GET(double, __VA_ARGS__)
#define GETC(...) GET(char, __VA_ARGS__)

struct hsh {
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
    x += FIXED_RANDOM;
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
};

const ll mxN = 1e5;

vector<ar<ll, 2>> g[mxN];

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

  GETI(n, m, k);
  REP(mm, m) {
    GETI(i, j, w); --i, --j;
    g[i].push_back({j, w});
    g[j].push_back({i, w});
  }
  vector<ll> a(k);
  REP(i, k) cin >> a[i], --a[i];

  vector<bool> special(n);
  for (ll x : a) special[x] = true;

  vector<ll> vis_cnt(n);
  vector<ar<ll, 3>> vis(n, {-1, -1, -1}), dist(n, {-1, -1, -1});

  priority_queue<ar<ll, 3>, vector<ar<ll, 3>>, greater<ar<ll, 3>>> pq;
  for (ll x : a) pq.push({0, x, x});

  while (pq.size()) {
    auto [dhere, cur, source] = pq.top();
    pq.pop();

    if (vis_cnt[cur]==3) continue;

    DEBUG(cur);
    DEBUG(vis_cnt[cur]);
    DEBUG(vis[cur]);
    DEBUG(dist[cur]);

    bool ok = true;
    REP(p, vis_cnt[cur]) if (vis[cur][p] == source) ok = false;
    if (!ok) continue;

    vis[cur][vis_cnt[cur]] = source;
    dist[cur][vis_cnt[cur]] = dhere;
    ++vis_cnt[cur];

    for (auto [nxt, w] : g[cur]) {
      if (vis_cnt[nxt] == 3) continue;
      bool ok = true;
      REP(p, vis_cnt[nxt]) if (vis[nxt][p] == source) ok = false;
      if (!ok) continue;

      pq.push({dhere+w, nxt, source});
    }
  }

  vector<ar<ll, 3>> pairs;
  REP(i, n)
    if (special[i])
      REP(p, vis_cnt[i])
        if (vis[i][p] != i) pairs.push_back({dist[i][p], min(i, vis[i][p]), max(i, vis[i][p])});

  sort(pairs.begin(), pairs.end());
  pairs.erase(unique(pairs.begin(), pairs.end()), pairs.end());

  DEBUG(pairs);
  int P = pairs.size();

  ll ans = 1LL<<60;

  REP(p0, min(P, 1000)) {
    auto [d0, i0, j0] = pairs[p0];
    REP(p1, min(P, 1000)) {
      auto [d1, i1, j1] = pairs[p1];
      if (i0 == i1) continue;
      if (i0 == j1) continue;
      if (j0 == i1) continue;
      if (j0 == j1) continue;
      ans = min(ans, d0+d1);
      break;
    }
  }

  cout << ans << '\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 12 / 12
• Subtask 3: 0 / 25
• Subtask 4: 0 / 58