Submission #337601

#	Time	Username	Problem	Language	Result	Execution time	Memory
337601		ncduy0303	Relay Marathon (NOI20_relaymarathon)	C++17	100 / 100	2778 ms	162616 KiB

RelayMarathon

#include <bits/stdc++.h>

using namespace std;

#define ar array
#define ll long long

const int MAX_N = 1e5 + 1;
const ll MOD = 1e9 + 7;
const ll INF = 1e9;

int V, E, K, head[MAX_N];
vector<int> d, dx1, dy1;
set<int> S;
bool skip[MAX_N];
vector<ar<int,2>> adj[MAX_N];
vector<ar<int,3>> el;
priority_queue<ar<int,2>, vector<ar<int,2>>, greater<ar<int,2>>> pq;

void dijk() {
    while (!pq.empty()) {
        int u = pq.top()[1];
        pq.pop();
        for (auto cur : adj[u]) {
            int v = cur[0], w = cur[1];
            if (skip[v]) continue;
            if (d[u] + w < d[v]) {
                d[v] = d[u] + w;
                pq.push({d[v], v});
                head[v] = head[u];
            }
        }
    }
}

void run(int s) {
    while (!pq.empty()) pq.pop();
    d.assign(V + 1, INF);
    d[s] = 0;
    head[s] = s;
    pq.push({0, s});
    dijk();
}

ar<int,3> find() {
    while (!pq.empty()) pq.pop();
    d.assign(V + 1, INF);
    for (int s : S) {
        if (skip[s]) continue;
        d[s] = 0;
        pq.push({0, s});
        head[s] = s;
    }
    dijk();
    int s1, e1, d1 = INF;
    for (auto [u, v, w] : el) {
        if (skip[u] || skip[v])  continue;
        if (d[u] == INF || d[v] == INF || head[u] == head[v])  continue;
        if (d1 > d[u] + w + d[v]) {
            d1 = d[u] + w + d[v];
            s1 = head[u], e1 = head[v];
        }
    }
    return {s1, e1, d1};
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    cin >> V >> E >> K;
    while (E--) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
        el.push_back({u, v, w});
    }
    for (int i = 1; i <= K; i++) {
        int u; cin >> u;
        S.insert(u);
    }

    auto [x1, y1, d1] = find();

    // x1 and y1 are now the closet pair among all special nodes
    // There are 2 cases:
    // Case #1: x1 and y1 are actually x1 and x2 => Run 2 separate Dijkstra on x1 and x2 to find the best y1, y2 using an O(N) technique
    // Case #2: x1 and y1 are still x1 and y1 => Just create a new graph without x1, y1 and repeat the same process to find x2, y2
    // Final answer is the minimum between the two cases

    // Case #1
    run(x1); dx1 = d;
    run(y1); dy1 = d;
    int c1 = -1, c2 = -1;
    for (int c : S) {
        if (c == x1 or c == y1)  continue;
        if (c1 == -1 || dy1[c] <= dy1[c1]) {
            c2 = c1;
            c1 = c;
        } else if(c2 == -1 || dy1[c] < dy1[c2]) {
            c2 = c;
        }
    }
    int ans = INF, a1 = -1, a2 = -1, a3 = -1, a4 = -1;
    if (dx1[c1] != INF && dy1[c2] != INF) {
        ans = dx1[c1] + dy1[c2];
        a1 = x1, a2 = c1, a3 = y1, a4 = c2;
    }
    for (int x2 : S) {
        if (x2 == x1 || x2 == y1 || x2 == c1)  continue;
        if (dx1[x2] != INF && dy1[c1] != INF) {
            if (ans > dx1[x2] + dy1[c1]) {
                ans = dx1[x2] + dy1[c1];
                a1 = x1, a2 = x2, a3 = y1, a4 = c1;
            }
        }
    }

    // Case #2: removing s1 and e1 before repeating the same process
    skip[x1] = skip[y1] = 1;
    auto [x2, y2, d2] = find();
    if (d1 != INF and d2 != INF) {
        if (ans > d1 + d2) {
            ans = d1 + d2;
            a1 = x1, a2 = y1, a3 = x2, a4 = y2;
        }
    }

    cout << ans;
}

Compilation message (stderr)

RelayMarathon.cpp: In function 'int main()':
RelayMarathon.cpp:107:20: warning: variable 'a1' set but not used [-Wunused-but-set-variable]
  107 |     int ans = INF, a1 = -1, a2 = -1, a3 = -1, a4 = -1;
      |                    ^~
RelayMarathon.cpp:107:29: warning: variable 'a2' set but not used [-Wunused-but-set-variable]
  107 |     int ans = INF, a1 = -1, a2 = -1, a3 = -1, a4 = -1;
      |                             ^~
RelayMarathon.cpp:107:38: warning: variable 'a3' set but not used [-Wunused-but-set-variable]
  107 |     int ans = INF, a1 = -1, a2 = -1, a3 = -1, a4 = -1;
      |                                      ^~
RelayMarathon.cpp:107:47: warning: variable 'a4' set but not used [-Wunused-but-set-variable]
  107 |     int ans = INF, a1 = -1, a2 = -1, a3 = -1, a4 = -1;
      |                                               ^~
RelayMarathon.cpp: In function 'std::array<int, 3> find()':
RelayMarathon.cpp:64:23: warning: 'e1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   64 |     return {s1, e1, d1};
      |                       ^
RelayMarathon.cpp:64:23: warning: 's1' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 1: 5 / 5
• Subtask 2: 12 / 12
• Subtask 3: 25 / 25
• Subtask 4: 58 / 58