oj.uz

Submission #367709

# Submission time Handle Problem Language Result Execution time Memory
367709 2021-02-18T04:00:23 Z arujbansal Relay Marathon (NOI20_relaymarathon) C++17
0 / 100
 3584 ms 75232 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <array>
#include <stack>
#include <queue>
#include <random>
#include <numeric>
#include <functional>
#include <chrono>
#include <utility>
#include <iomanip>
#include <assert.h>

using namespace std;

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)

#define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define rng_seed(x) mt19937 rng(x)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
// #define int long long

rng_init;

const int MXN = 1e5 + 5, INF = 1e9 + 5;
int N, M, K;
vector<pair<int, int>> g[MXN];

int dijkstra(const vector<int> &src, const vector<int> &sink) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

    vector<int> dist(N, INF);

    for (const auto &x : src) {
        dist[x] = 0;
        pq.emplace(0, x);
    }

    vector<bool> finish(N, false);
    for (const auto &x : sink)
        finish[x] = true;

    while (!pq.empty()) {
        auto cur = pq.top();
        pq.pop();

        int u = cur.second, cur_dist = cur.first;
        if (cur_dist > dist[u]) continue;

        if (finish[u])
            return cur_dist;

        for (const auto &[v, wt] : g[u]) {
            int new_dist = cur_dist + wt;

            if (new_dist < dist[v]) {
                dist[v] = new_dist;
                pq.emplace(new_dist, v);
            }
        }
    }

    int ans = INF;
    for (const auto &x : sink)
        ans = min(ans, dist[x]);

    return ans;
}

void solve() {
    cin >> N >> M >> K;

    for (int i = 0; i < M; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;

        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }

    vector<int> special(K);
    for (auto &x : special) {
        cin >> x;
        x--;
    }

    int ans = INF;

    for (int iter = 0; iter < 50; iter++) {
        for (int i = 0; i < 3; i++)
            shuffle(all(special), rng);

        vector<int> src[2], sink[2];
        
        for (int i = 0; i < K / 2; i++)
            src[i % 2].push_back(special[i]);

        for (int i = K / 2; i < K; i++)
            sink[i % 2].push_back(special[i]);

        ans = min(ans, dijkstra(src[0], sink[0]) + dijkstra(src[1], sink[1]));
    }

    cout << ans;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int TC = 1;
    // cin >> TC;
    while (TC--) solve();
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 3 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Incorrect 2 ms 2668 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 3 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Incorrect 2 ms 2668 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 5860 KB Output is correct
2 Correct 11 ms 3564 KB Output is correct
3 Correct 3584 ms 65800 KB Output is correct
4 Correct 1943 ms 33080 KB Output is correct
5 Correct 1447 ms 9952 KB Output is correct
6 Correct 486 ms 8036 KB Output is correct
7 Correct 1743 ms 10392 KB Output is correct
8 Correct 314 ms 5988 KB Output is correct
9 Correct 344 ms 7740 KB Output is correct
10 Correct 299 ms 6500 KB Output is correct
11 Correct 3502 ms 67864 KB Output is correct
12 Correct 258 ms 6756 KB Output is correct
13 Correct 2037 ms 31024 KB Output is correct
14 Correct 271 ms 12588 KB Output is correct
15 Correct 3404 ms 74636 KB Output is correct
16 Correct 290 ms 6628 KB Output is correct
17 Correct 1554 ms 52876 KB Output is correct
18 Correct 18 ms 3692 KB Output is correct
19 Correct 2116 ms 75232 KB Output is correct
20 Correct 272 ms 11928 KB Output is correct
21 Correct 518 ms 11500 KB Output is correct
22 Correct 179 ms 7644 KB Output is correct
23 Correct 32 ms 5612 KB Output is correct
24 Correct 3279 ms 61576 KB Output is correct
25 Correct 239 ms 9700 KB Output is correct
26 Correct 225 ms 7140 KB Output is correct
27 Incorrect 418 ms 8780 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #4
0 / 58.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 3 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Incorrect 2 ms 2668 KB Output isn't correct
7 Halted 0 ms 0 KB -