Submission #1178529

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178529		_callmelucian	Relay Marathon (NOI20_relaymarathon)	C++20	5 / 100	6094 ms	139240 KiB

RelayMarathon

#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) {
        pii cur = {cand, source};
        insert(upper_bound(all((*this)), make_pair(cand, INT_MAX)), cur);

        set<int> vist;
        for (int i = 0; i < size(); i++) {
            if (vist.count((*this)[i].second)) {
                erase((*this).begin() + i);
                if ((*this)[i] == cur) return 0;
                break;
            }
            vist.insert((*this)[i].second);
        }
        if (size() > maxStage) {
            if (back() == cur) return 0;
            pop_back();
        }
        return 1;
    }
} 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;
}

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