Submission #1178394

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178394		_callmelucian	Relay Marathon (NOI20_relaymarathon)	C++17	17 / 100	6097 ms	271396 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;

int spec[mn], dist[maxStage][mn], optSource[maxStage][mn], n, m, k;
vector<pii> adj[mn], path[mn];
set<int> visitedSource[mn];
priority_queue<tpl> pq;

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 >= 1; 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));
    }
};

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

    void update (int a, int b, int val, int k, int l, int r) {
        if (b < l || r < a) return;
        if (a <= l && r <= b) return lazy[k] = min(lazy[k], val), void();
        int mid = (l + r) >> 1;
        update(a, b, val, k << 1, l, mid);
        update(a, b, val, k << 1 | 1, mid + 1, r);
    }

    int query (int pos, int k, int l, int r) {
        int ans = lazy[k];
        for (; l < r;) {
            int mid = (l + r) >> 1;
            if (pos <= mid) k <<= 1, r = mid;
            else k <<= 1, k |= 1, l = mid + 1;
            ans = min(ans, lazy[k]);
        }
        return ans;
    }
};

void addPath (int u, int v, int w) {
    if (w == INT_MAX) return;
    path[max(u, v)].emplace_back(min(u, v), w);
}

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 <= n; i++)
        for (int j = 0; j < maxStage; j++) dist[j][i] = INT_MAX;
    for (int i = 1; i <= k; i++) {
        cin >> spec[i];
        pq.emplace(0, spec[i], spec[i]);
    }

    /// multi-core dijkstra
    while (pq.size()) {
        int dst, u, source; tie(dst, u, source) = pq.top(); pq.pop();
        if (visitedSource[u].size() >= maxStage || visitedSource[u].count(source)) continue;

        int stage = visitedSource[u].size();
        dst = -dst, dist[stage][u] = dst, optSource[stage][u] = source;
        visitedSource[u].insert(source);

        for (pii item : adj[u]) {
            int v, w; tie(v, w) = item;
            if (dst + w < dist[maxStage - 1][v])
                if (!visitedSource[v].count(source)) pq.emplace(-(dst + w), v, source);
        }
    }

    /// solve
    for (int i = 1; i <= k; i++) {
        int u = spec[i];
        for (int j = 1; j < maxStage; j++)
            addPath(u, optSource[j][u], dist[j][u]);
    }

    int ans = INT_MAX;
    IT treeLeft(n), treeRight(n);
    ITRange treeRange(n);

    for (int i = 1; i <= n; i++) {
        for (pii item : path[i]) {
            int j, w; tie(j, w) = item;
            int cur = min({treeRight.query(1, j - 1, 1, 1, n),
                           treeLeft.query(j + 1, n, 1, 1, n),
                           treeRange.query(j, 1, 1, n)});
            if (cur != INT_MAX) ans = min(ans, cur + w);
        }
        for (pii item : path[i]) {
            int j, w; tie(j, w) = item;
            treeLeft.update(j, w, 1, 1, n);
            treeRight.update(i, w, 1, 1, n);
            if (j + 1 <= i - 1)
                treeRange.update(j + 1, i - 1, w, 1, 1, n);
        }
    }
    cout << (ans == INT_MAX ? -1 : ans);

    return 0;
}

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