oj.uz

Submission #383053

# Submission time Handle Problem Language Result Execution time Memory
383053 2021-03-28T18:29:02 Z Hegdahl Relay Marathon (NOI20_relaymarathon) C++17
5 / 100
 6000 ms 146636 KB 
#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 INF = 1LL<<60;
const int mxN = 1e5;

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

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll ans = INF;

template<class IsStart, class IsTarget>
ll solve(ll n, IsStart is_start, IsTarget is_target) {
  
  vector<bool> vis(n);
  priority_queue<ar<ll, 2>, vector<ar<ll, 2>>, greater<ar<ll, 2>>> pq;
  REP(i, n) if (is_start(i)) pq.push({0, i});

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

    if (dhere > ans) return INF;

    if (vis[cur]) continue;
    if (is_target(cur)) return dhere;

    vis[cur] = true;

    for (auto [nxt, w] : g[cur]) {
      if (vis[nxt]) continue;
      pq.push({dhere+w, nxt});
    }
  }

  return INF;
}

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), pof(n, -1);
  REP(i, k) cin >> a[i], --a[i];

  REP(t, 100) {
    shuffle(a.begin(), a.end(), rng);
    REP(i, k) pof[a[i]] = i;

    ll d1 = solve(n,
        [&](ll i){return pof[i] >= 0*k/4 && pof[i] < 1*k/4;},
        [&](ll i){return pof[i] >= 1*k/4 && pof[i] < 2*k/4;}
    );                                                  
    ll d2 = solve(n,                                    
        [&](ll i){return pof[i] >= 2*k/4 && pof[i] < 3*k/4;},
        [&](ll i){return pof[i] >= 3*k/4 && pof[i] < 4*k/4;}
    );

    ans = min(ans, d1+d2);
  }

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2668 KB Output is correct
2 Correct 5 ms 2796 KB Output is correct
3 Correct 4 ms 2668 KB Output is correct
4 Correct 3 ms 2668 KB Output is correct
5 Correct 3 ms 2668 KB Output is correct
6 Correct 4 ms 2668 KB Output is correct
7 Correct 5 ms 2796 KB Output is correct
8 Correct 5 ms 2796 KB Output is correct
9 Correct 3 ms 2668 KB Output is correct
10 Correct 3 ms 2668 KB Output is correct
11 Correct 3 ms 2668 KB Output is correct
12 Correct 3 ms 2668 KB Output is correct
13 Correct 5 ms 2796 KB Output is correct
14 Correct 5 ms 2796 KB Output is correct
15 Correct 5 ms 2796 KB Output is correct
16 Correct 3 ms 2668 KB Output is correct
17 Correct 5 ms 2796 KB Output is correct
18 Correct 3 ms 2668 KB Output is correct
19 Correct 6 ms 2796 KB Output is correct
20 Correct 4 ms 2668 KB Output is correct
21 Correct 4 ms 2796 KB Output is correct
22 Correct 3 ms 2668 KB Output is correct
23 Correct 4 ms 2796 KB Output is correct
24 Correct 3 ms 2668 KB Output is correct
25 Correct 4 ms 2668 KB Output is correct
26 Correct 3 ms 2668 KB Output is correct
27 Correct 4 ms 2668 KB Output is correct
28 Correct 6 ms 2796 KB Output is correct
29 Correct 5 ms 2796 KB Output is correct
30 Correct 5 ms 2796 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2668 KB Output is correct
2 Correct 5 ms 2796 KB Output is correct
3 Correct 4 ms 2668 KB Output is correct
4 Correct 3 ms 2668 KB Output is correct
5 Correct 3 ms 2668 KB Output is correct
6 Correct 4 ms 2668 KB Output is correct
7 Correct 5 ms 2796 KB Output is correct
8 Correct 5 ms 2796 KB Output is correct
9 Correct 3 ms 2668 KB Output is correct
10 Correct 3 ms 2668 KB Output is correct
11 Correct 3 ms 2668 KB Output is correct
12 Correct 3 ms 2668 KB Output is correct
13 Correct 5 ms 2796 KB Output is correct
14 Correct 5 ms 2796 KB Output is correct
15 Correct 5 ms 2796 KB Output is correct
16 Correct 3 ms 2668 KB Output is correct
17 Correct 5 ms 2796 KB Output is correct
18 Correct 3 ms 2668 KB Output is correct
19 Correct 6 ms 2796 KB Output is correct
20 Correct 4 ms 2668 KB Output is correct
21 Correct 4 ms 2796 KB Output is correct
22 Correct 3 ms 2668 KB Output is correct
23 Correct 4 ms 2796 KB Output is correct
24 Correct 3 ms 2668 KB Output is correct
25 Correct 4 ms 2668 KB Output is correct
26 Correct 3 ms 2668 KB Output is correct
27 Correct 4 ms 2668 KB Output is correct
28 Correct 6 ms 2796 KB Output is correct
29 Correct 5 ms 2796 KB Output is correct
30 Correct 5 ms 2796 KB Output is correct
31 Correct 7 ms 2668 KB Output is correct
32 Correct 6 ms 2796 KB Output is correct
33 Correct 10 ms 2796 KB Output is correct
34 Correct 4 ms 2668 KB Output is correct
35 Correct 4 ms 2668 KB Output is correct
36 Incorrect 17 ms 3052 KB Output isn't correct
37 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 7276 KB Output is correct
2 Correct 30 ms 3948 KB Output is correct
3 Execution timed out 6056 ms 146636 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 58.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2668 KB Output is correct
2 Correct 5 ms 2796 KB Output is correct
3 Correct 4 ms 2668 KB Output is correct
4 Correct 3 ms 2668 KB Output is correct
5 Correct 3 ms 2668 KB Output is correct
6 Correct 4 ms 2668 KB Output is correct
7 Correct 5 ms 2796 KB Output is correct
8 Correct 5 ms 2796 KB Output is correct
9 Correct 3 ms 2668 KB Output is correct
10 Correct 3 ms 2668 KB Output is correct
11 Correct 3 ms 2668 KB Output is correct
12 Correct 3 ms 2668 KB Output is correct
13 Correct 5 ms 2796 KB Output is correct
14 Correct 5 ms 2796 KB Output is correct
15 Correct 5 ms 2796 KB Output is correct
16 Correct 3 ms 2668 KB Output is correct
17 Correct 5 ms 2796 KB Output is correct
18 Correct 3 ms 2668 KB Output is correct
19 Correct 6 ms 2796 KB Output is correct
20 Correct 4 ms 2668 KB Output is correct
21 Correct 4 ms 2796 KB Output is correct
22 Correct 3 ms 2668 KB Output is correct
23 Correct 4 ms 2796 KB Output is correct
24 Correct 3 ms 2668 KB Output is correct
25 Correct 4 ms 2668 KB Output is correct
26 Correct 3 ms 2668 KB Output is correct
27 Correct 4 ms 2668 KB Output is correct
28 Correct 6 ms 2796 KB Output is correct
29 Correct 5 ms 2796 KB Output is correct
30 Correct 5 ms 2796 KB Output is correct
31 Correct 7 ms 2668 KB Output is correct
32 Correct 6 ms 2796 KB Output is correct
33 Correct 10 ms 2796 KB Output is correct
34 Correct 4 ms 2668 KB Output is correct
35 Correct 4 ms 2668 KB Output is correct
36 Incorrect 17 ms 3052 KB Output isn't correct
37 Halted 0 ms 0 KB -