Submission #1178533

#TimeUsernameProblemLanguageResultExecution timeMemory
1178533_callmelucianRelay Marathon (NOI20_relaymarathon)C++20
100 / 100
1714 ms107772 KiB
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using pl = pair<ll,ll>;
using pii = pair<int,int>;
using tpl = tuple<int,int,int>;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 1e5 + 5;
const int maxStage = 4;

struct candidates : vector<pii> {
    bool push (int cand, int source) {
        int inserted = -1;
        for (int i = 0; i < size(); i++) {
            int cur, s; tie(cur, s) = (*this)[i];
            if (cand < cur) {
                inserted = i;
                insert((*this).begin() + i, make_pair(cand, source));
                break;
            }
            else if (s == source) return 0;
        }
        if (inserted != -1) {
            for (int i = inserted + 1; i < size(); i++)
                if ((*this)[i].second == source)
                    return erase((*this).begin() + i), 1;
            if (size() > maxStage) return pop_back(), 1;
        }
        else {
            if (size() < maxStage) return emplace_back(cand, source), 1;
            else return 0;
        }
    }
} dist[mn];

struct IT {
    vector<int> tr;
    IT (int sz) : tr(4 * sz, INT_MAX) {}

    void update (int pos, int val, int k, int l, int r) {
        for (; l < r;) {
            int mid = (l + r) >> 1;
            if (pos <= mid) k <<= 1, r = mid;
            else k <<= 1, k |= 1, l = mid + 1;
        }
        tr[k] = min(tr[k], val);
        for (k >>= 1; k; k >>= 1)
            tr[k]= min(tr[k << 1], tr[k << 1 | 1]);
    }

    int query (int a, int b, int k, int l, int r) {
        if (b < l || r < a) return INT_MAX;
        if (a <= l && r <= b) return tr[k];
        int mid = (l + r) >> 1;
        return min(query(a, b, k << 1, l, mid), query(a, b, k << 1 | 1, mid + 1, r));
    }
};

priority_queue<tpl, vector<tpl>, greater<tpl>> pq;
vector<pii> adj[mn], path[mn];
vector<int> visSource[mn];
int visTime[mn], spec[mn], n, m, k;

bool check (int u, int targ) {
    return find(all(visSource[u]), targ) != visSource[u].end();
}

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

    /// read input & preprocess
    cin >> n >> m >> k;
    while (m--) {
        int a, b, c; cin >> a >> b >> c;
        adj[a].emplace_back(b, c);
        adj[b].emplace_back(a, c);
    }
    for (int i = 1; i <= k; i++) {
        cin >> spec[i];
        pq.emplace(0, spec[i], spec[i]);
        dist[spec[i]].emplace_back(0, spec[i]);
    }

    /// multi-core dijkstra
    int threshold = 0;
    while (pq.size() && threshold < 5 * n) {
        int dst, u, source; tie(dst, u, source) = pq.top(); pq.pop();
        if (visTime[u] == maxStage || check(u, source)) continue;
        visTime[u]++, threshold++;

        for (pii item : adj[u]) {
            int v, w; tie(v, w) = item;
            if (dist[v].push(dst + w, source))
                pq.emplace(dst + w, v, source);
        }
    }

    /// combine 2 paths
    for (int i = 1; i <= k; i++) {
        int u = spec[i];
        for (auto [dist, source] : dist[u])
            if (u != source) path[min(source, u)].emplace_back(max(source, u), dist);
    }

    IT tree(n); int ans = INT_MAX;
    for (int i = 1; i <= n; i++) {
        for (auto [v, weight] : path[i]) {
            int cur = min({tree.query(1, i - 1, 1, 1, n),
                           tree.query(i + 1, v - 1, 1, 1, n),
                           tree.query(v + 1, n, 1, 1, n)});
            if (cur != INT_MAX) ans = min(ans, weight + cur);
        }
        for (auto [v, weight] : path[i])
            tree.update(v, weight, 1, 1, n);
    }
    cout << (ans == INT_MAX ? -1 : ans);

    return 0;
}

Compilation message (stderr)

RelayMarathon.cpp: In member function 'bool candidates::push(int, int)':
RelayMarathon.cpp:38:5: warning: control reaches end of non-void function [-Wreturn-type]
   38 |     }
      |     ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...