oj.uz

Submission #367710

# Submission time Handle Problem Language Result Execution time Memory
367710 2021-02-18T04:04:07 Z arujbansal Relay Marathon (NOI20_relaymarathon) C++17
0 / 100
 3487 ms 67816 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++) {
        shuffle(all(special), rng);

        vector<int> src[2], sink[2];
        
        for (int i = 0; i < K; i++) {
            if (i < K / 4) src[0].push_back(special[i]);
            else if (i < K / 2) sink[0].push_back(special[i]);
            else if (i < 3 * K / 4) src[1].push_back(special[i]);
            else sink[1].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 2796 KB Output is correct
3 Correct 3 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 3 ms 2668 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct
7 Correct 3 ms 2796 KB Output is correct
8 Correct 3 ms 2796 KB Output is correct
9 Correct 2 ms 2668 KB Output is correct
10 Correct 2 ms 2668 KB Output is correct
11 Correct 3 ms 2668 KB Output is correct
12 Correct 2 ms 2668 KB Output is correct
13 Incorrect 3 ms 2796 KB Output isn't correct
14 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 2796 KB Output is correct
3 Correct 3 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 3 ms 2668 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct
7 Correct 3 ms 2796 KB Output is correct
8 Correct 3 ms 2796 KB Output is correct
9 Correct 2 ms 2668 KB Output is correct
10 Correct 2 ms 2668 KB Output is correct
11 Correct 3 ms 2668 KB Output is correct
12 Correct 2 ms 2668 KB Output is correct
13 Incorrect 3 ms 2796 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 6244 KB Output is correct
2 Correct 12 ms 3820 KB Output is correct
3 Correct 3487 ms 66068 KB Output is correct
4 Correct 1855 ms 33504 KB Output is correct
5 Correct 1566 ms 10332 KB Output is correct
6 Correct 497 ms 8340 KB Output is correct
7 Correct 1715 ms 10304 KB Output is correct
8 Correct 356 ms 6124 KB Output is correct
9 Correct 344 ms 7780 KB Output is correct
10 Correct 274 ms 6636 KB Output is correct
11 Correct 3413 ms 67816 KB Output is correct
12 Correct 266 ms 6884 KB Output is correct
13 Correct 1912 ms 21620 KB Output is correct
14 Correct 246 ms 9684 KB Output is correct
15 Correct 3308 ms 66828 KB Output is correct
16 Correct 317 ms 5740 KB Output is correct
17 Correct 1545 ms 48548 KB Output is correct
18 Correct 12 ms 3692 KB Output is correct
19 Correct 2118 ms 67060 KB Output is correct
20 Correct 266 ms 9252 KB Output is correct
21 Correct 473 ms 9300 KB Output is correct
22 Correct 163 ms 6500 KB Output is correct
23 Incorrect 34 ms 5100 KB Output isn't correct
24 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 2796 KB Output is correct
3 Correct 3 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 3 ms 2668 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct
7 Correct 3 ms 2796 KB Output is correct
8 Correct 3 ms 2796 KB Output is correct
9 Correct 2 ms 2668 KB Output is correct
10 Correct 2 ms 2668 KB Output is correct
11 Correct 3 ms 2668 KB Output is correct
12 Correct 2 ms 2668 KB Output is correct
13 Incorrect 3 ms 2796 KB Output isn't correct
14 Halted 0 ms 0 KB -