oj.uz

Submission #383062

# Submission time Handle Problem Language Result Execution time Memory
383062 2021-03-28T18:44:41 Z Hegdahl Relay Marathon (NOI20_relaymarathon) C++17
100 / 100
 5649 ms 266444 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());

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

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

    if (dhere > cut) return {INF, -1, -1};

    if (vis[cur]) continue;
    if (is_target(cur)) return {dhere, cur, source};

    vis[cur] = true;

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

  return {INF, -1, -1};
}

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

  auto t0 = chrono::steady_clock::now();

  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];

  ll ans = INF;

  while (true) {
    auto t1 = chrono::steady_clock::now();
    if (chrono::duration_cast<chrono::milliseconds>(t1-t0).count() > 5500) break;

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

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

    if (target1 == -1) continue;

    auto [d2, target2, source2] = solve(n,                                    
        [&](ll i){return pof[i] >= 0*k/4 && pof[i] < 2*k/4 && i != target1 && i != source1;},
        [&](ll i){return pof[i] >= 2*k/4 && pof[i] < 4*k/4 && i != target1 && i != source1;},
        ans-d1
    );

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

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5456 ms 2748 KB Output is correct
2 Correct 5454 ms 2868 KB Output is correct
3 Correct 5497 ms 2748 KB Output is correct
4 Correct 5502 ms 2668 KB Output is correct
5 Correct 5469 ms 2748 KB Output is correct
6 Correct 5458 ms 2748 KB Output is correct
7 Correct 5472 ms 2844 KB Output is correct
8 Correct 5466 ms 2860 KB Output is correct
9 Correct 5493 ms 2744 KB Output is correct
10 Correct 5461 ms 2748 KB Output is correct
11 Correct 5456 ms 2752 KB Output is correct
12 Correct 5462 ms 2752 KB Output is correct
13 Correct 5447 ms 2860 KB Output is correct
14 Correct 5471 ms 2848 KB Output is correct
15 Correct 5457 ms 2924 KB Output is correct
16 Correct 5479 ms 2752 KB Output is correct
17 Correct 5486 ms 2836 KB Output is correct
18 Correct 5485 ms 2752 KB Output is correct
19 Correct 5459 ms 2924 KB Output is correct
20 Correct 5489 ms 2796 KB Output is correct
21 Correct 5488 ms 2812 KB Output is correct
22 Correct 5496 ms 2744 KB Output is correct
23 Correct 5451 ms 2924 KB Output is correct
24 Correct 5494 ms 2752 KB Output is correct
25 Correct 5470 ms 2748 KB Output is correct
26 Correct 5501 ms 2668 KB Output is correct
27 Correct 5466 ms 2748 KB Output is correct
28 Correct 5456 ms 2924 KB Output is correct
29 Correct 5474 ms 2972 KB Output is correct
30 Correct 5452 ms 2924 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5456 ms 2748 KB Output is correct
2 Correct 5454 ms 2868 KB Output is correct
3 Correct 5497 ms 2748 KB Output is correct
4 Correct 5502 ms 2668 KB Output is correct
5 Correct 5469 ms 2748 KB Output is correct
6 Correct 5458 ms 2748 KB Output is correct
7 Correct 5472 ms 2844 KB Output is correct
8 Correct 5466 ms 2860 KB Output is correct
9 Correct 5493 ms 2744 KB Output is correct
10 Correct 5461 ms 2748 KB Output is correct
11 Correct 5456 ms 2752 KB Output is correct
12 Correct 5462 ms 2752 KB Output is correct
13 Correct 5447 ms 2860 KB Output is correct
14 Correct 5471 ms 2848 KB Output is correct
15 Correct 5457 ms 2924 KB Output is correct
16 Correct 5479 ms 2752 KB Output is correct
17 Correct 5486 ms 2836 KB Output is correct
18 Correct 5485 ms 2752 KB Output is correct
19 Correct 5459 ms 2924 KB Output is correct
20 Correct 5489 ms 2796 KB Output is correct
21 Correct 5488 ms 2812 KB Output is correct
22 Correct 5496 ms 2744 KB Output is correct
23 Correct 5451 ms 2924 KB Output is correct
24 Correct 5494 ms 2752 KB Output is correct
25 Correct 5470 ms 2748 KB Output is correct
26 Correct 5501 ms 2668 KB Output is correct
27 Correct 5466 ms 2748 KB Output is correct
28 Correct 5456 ms 2924 KB Output is correct
29 Correct 5474 ms 2972 KB Output is correct
30 Correct 5452 ms 2924 KB Output is correct
31 Correct 5493 ms 2796 KB Output is correct
32 Correct 5449 ms 2796 KB Output is correct
33 Correct 5496 ms 2924 KB Output is correct
34 Correct 5495 ms 2796 KB Output is correct
35 Correct 5466 ms 2756 KB Output is correct
36 Correct 5456 ms 3304 KB Output is correct
37 Correct 5466 ms 3780 KB Output is correct
38 Correct 5478 ms 2812 KB Output is correct
39 Correct 5476 ms 9512 KB Output is correct
40 Correct 5462 ms 5028 KB Output is correct
41 Correct 5482 ms 2832 KB Output is correct
42 Correct 5499 ms 4716 KB Output is correct
43 Correct 5487 ms 3008 KB Output is correct
44 Correct 5453 ms 2828 KB Output is correct
45 Correct 5477 ms 2796 KB Output is correct
46 Correct 5477 ms 12308 KB Output is correct
47 Correct 5500 ms 3792 KB Output is correct
48 Correct 5479 ms 8664 KB Output is correct
49 Correct 5477 ms 10244 KB Output is correct
50 Correct 5503 ms 2796 KB Output is correct
51 Correct 5478 ms 2924 KB Output is correct
52 Correct 5481 ms 2924 KB Output is correct
53 Correct 5503 ms 5376 KB Output is correct
54 Correct 5476 ms 8224 KB Output is correct
55 Correct 5493 ms 2796 KB Output is correct
56 Correct 5478 ms 2772 KB Output is correct
57 Correct 5495 ms 2800 KB Output is correct
58 Correct 5498 ms 9848 KB Output is correct
59 Correct 5451 ms 2752 KB Output is correct
60 Correct 5499 ms 2876 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5473 ms 7276 KB Output is correct
2 Correct 5450 ms 3948 KB Output is correct
3 Correct 5636 ms 191540 KB Output is correct
4 Correct 5520 ms 77152 KB Output is correct
5 Correct 5492 ms 17664 KB Output is correct
6 Correct 5472 ms 11184 KB Output is correct
7 Correct 5472 ms 22032 KB Output is correct
8 Correct 5495 ms 8764 KB Output is correct
9 Correct 5476 ms 12284 KB Output is correct
10 Correct 5439 ms 10088 KB Output is correct
11 Correct 5620 ms 216108 KB Output is correct
12 Correct 5460 ms 10720 KB Output is correct
13 Correct 5309 ms 64584 KB Output is correct
14 Correct 5389 ms 18428 KB Output is correct
15 Correct 5581 ms 213468 KB Output is correct
16 Correct 5432 ms 8184 KB Output is correct
17 Correct 5496 ms 124100 KB Output is correct
18 Correct 5387 ms 4076 KB Output is correct
19 Correct 5451 ms 164064 KB Output is correct
20 Correct 5473 ms 17372 KB Output is correct
21 Correct 5481 ms 16592 KB Output is correct
22 Correct 5458 ms 9588 KB Output is correct
23 Correct 5476 ms 6508 KB Output is correct
24 Correct 5515 ms 201336 KB Output is correct
25 Correct 5471 ms 12332 KB Output is correct
26 Correct 5471 ms 8720 KB Output is correct
27 Correct 5446 ms 11248 KB Output is correct
28 Correct 5450 ms 5228 KB Output is correct
29 Correct 5458 ms 17764 KB Output is correct
30 Correct 5484 ms 33664 KB Output is correct

Subtask #4
58.0 / 58.0

# Verdict Execution time Memory Grader output
1 Correct 5456 ms 2748 KB Output is correct
2 Correct 5454 ms 2868 KB Output is correct
3 Correct 5497 ms 2748 KB Output is correct
4 Correct 5502 ms 2668 KB Output is correct
5 Correct 5469 ms 2748 KB Output is correct
6 Correct 5458 ms 2748 KB Output is correct
7 Correct 5472 ms 2844 KB Output is correct
8 Correct 5466 ms 2860 KB Output is correct
9 Correct 5493 ms 2744 KB Output is correct
10 Correct 5461 ms 2748 KB Output is correct
11 Correct 5456 ms 2752 KB Output is correct
12 Correct 5462 ms 2752 KB Output is correct
13 Correct 5447 ms 2860 KB Output is correct
14 Correct 5471 ms 2848 KB Output is correct
15 Correct 5457 ms 2924 KB Output is correct
16 Correct 5479 ms 2752 KB Output is correct
17 Correct 5486 ms 2836 KB Output is correct
18 Correct 5485 ms 2752 KB Output is correct
19 Correct 5459 ms 2924 KB Output is correct
20 Correct 5489 ms 2796 KB Output is correct
21 Correct 5488 ms 2812 KB Output is correct
22 Correct 5496 ms 2744 KB Output is correct
23 Correct 5451 ms 2924 KB Output is correct
24 Correct 5494 ms 2752 KB Output is correct
25 Correct 5470 ms 2748 KB Output is correct
26 Correct 5501 ms 2668 KB Output is correct
27 Correct 5466 ms 2748 KB Output is correct
28 Correct 5456 ms 2924 KB Output is correct
29 Correct 5474 ms 2972 KB Output is correct
30 Correct 5452 ms 2924 KB Output is correct
31 Correct 5493 ms 2796 KB Output is correct
32 Correct 5449 ms 2796 KB Output is correct
33 Correct 5496 ms 2924 KB Output is correct
34 Correct 5495 ms 2796 KB Output is correct
35 Correct 5466 ms 2756 KB Output is correct
36 Correct 5456 ms 3304 KB Output is correct
37 Correct 5466 ms 3780 KB Output is correct
38 Correct 5478 ms 2812 KB Output is correct
39 Correct 5476 ms 9512 KB Output is correct
40 Correct 5462 ms 5028 KB Output is correct
41 Correct 5482 ms 2832 KB Output is correct
42 Correct 5499 ms 4716 KB Output is correct
43 Correct 5487 ms 3008 KB Output is correct
44 Correct 5453 ms 2828 KB Output is correct
45 Correct 5477 ms 2796 KB Output is correct
46 Correct 5477 ms 12308 KB Output is correct
47 Correct 5500 ms 3792 KB Output is correct
48 Correct 5479 ms 8664 KB Output is correct
49 Correct 5477 ms 10244 KB Output is correct
50 Correct 5503 ms 2796 KB Output is correct
51 Correct 5478 ms 2924 KB Output is correct
52 Correct 5481 ms 2924 KB Output is correct
53 Correct 5503 ms 5376 KB Output is correct
54 Correct 5476 ms 8224 KB Output is correct
55 Correct 5493 ms 2796 KB Output is correct
56 Correct 5478 ms 2772 KB Output is correct
57 Correct 5495 ms 2800 KB Output is correct
58 Correct 5498 ms 9848 KB Output is correct
59 Correct 5451 ms 2752 KB Output is correct
60 Correct 5499 ms 2876 KB Output is correct
61 Correct 5473 ms 7276 KB Output is correct
62 Correct 5450 ms 3948 KB Output is correct
63 Correct 5636 ms 191540 KB Output is correct
64 Correct 5520 ms 77152 KB Output is correct
65 Correct 5492 ms 17664 KB Output is correct
66 Correct 5472 ms 11184 KB Output is correct
67 Correct 5472 ms 22032 KB Output is correct
68 Correct 5495 ms 8764 KB Output is correct
69 Correct 5476 ms 12284 KB Output is correct
70 Correct 5439 ms 10088 KB Output is correct
71 Correct 5620 ms 216108 KB Output is correct
72 Correct 5460 ms 10720 KB Output is correct
73 Correct 5309 ms 64584 KB Output is correct
74 Correct 5389 ms 18428 KB Output is correct
75 Correct 5581 ms 213468 KB Output is correct
76 Correct 5432 ms 8184 KB Output is correct
77 Correct 5496 ms 124100 KB Output is correct
78 Correct 5387 ms 4076 KB Output is correct
79 Correct 5451 ms 164064 KB Output is correct
80 Correct 5473 ms 17372 KB Output is correct
81 Correct 5481 ms 16592 KB Output is correct
82 Correct 5458 ms 9588 KB Output is correct
83 Correct 5476 ms 6508 KB Output is correct
84 Correct 5515 ms 201336 KB Output is correct
85 Correct 5471 ms 12332 KB Output is correct
86 Correct 5471 ms 8720 KB Output is correct
87 Correct 5446 ms 11248 KB Output is correct
88 Correct 5450 ms 5228 KB Output is correct
89 Correct 5458 ms 17764 KB Output is correct
90 Correct 5484 ms 33664 KB Output is correct
91 Correct 5448 ms 12928 KB Output is correct
92 Correct 5411 ms 250764 KB Output is correct
93 Correct 5481 ms 21836 KB Output is correct
94 Correct 5493 ms 104536 KB Output is correct
95 Correct 5432 ms 4204 KB Output is correct
96 Correct 5457 ms 4332 KB Output is correct
97 Correct 5481 ms 27396 KB Output is correct
98 Correct 5456 ms 12496 KB Output is correct
99 Correct 5486 ms 12920 KB Output is correct
100 Correct 5411 ms 234544 KB Output is correct
101 Correct 5481 ms 69156 KB Output is correct
102 Correct 5494 ms 76896 KB Output is correct
103 Correct 5544 ms 205664 KB Output is correct
104 Correct 5460 ms 168764 KB Output is correct
105 Correct 5498 ms 9044 KB Output is correct
106 Correct 5400 ms 179440 KB Output is correct
107 Correct 5503 ms 40348 KB Output is correct
108 Correct 5506 ms 17792 KB Output is correct
109 Correct 5505 ms 5740 KB Output is correct
110 Correct 5421 ms 8480 KB Output is correct
111 Correct 5424 ms 16172 KB Output is correct
112 Correct 5298 ms 257924 KB Output is correct
113 Correct 5649 ms 266444 KB Output is correct
114 Correct 5486 ms 19932 KB Output is correct
115 Correct 5459 ms 103940 KB Output is correct
116 Correct 5530 ms 245000 KB Output is correct
117 Correct 5532 ms 203124 KB Output is correct
118 Correct 5209 ms 158000 KB Output is correct
119 Correct 5519 ms 192152 KB Output is correct
120 Correct 5414 ms 91856 KB Output is correct