oj.uz

Submission #367708

# Submission time Handle Problem Language Result Execution time Memory
367708 2021-02-18T03:59:46 Z arujbansal Relay Marathon (NOI20_relaymarathon) C++17
0 / 100
 3381 ms 75944 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 < 45; 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 Incorrect 2 ms 2668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 5860 KB Output is correct
2 Correct 11 ms 3692 KB Output is correct
3 Correct 3381 ms 65836 KB Output is correct
4 Correct 1822 ms 33248 KB Output is correct
5 Correct 1396 ms 9936 KB Output is correct
6 Correct 473 ms 8296 KB Output is correct
7 Correct 1509 ms 13156 KB Output is correct
8 Correct 348 ms 7140 KB Output is correct
9 Correct 270 ms 9524 KB Output is correct
10 Correct 233 ms 8036 KB Output is correct
11 Correct 3239 ms 75944 KB Output is correct
12 Incorrect 210 ms 8292 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 58.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2668 KB Output isn't correct
2 Halted 0 ms 0 KB -