Submission #744297

#	Time	Username	Problem	Language	Result	Execution time	Memory
744297		nhphucqt	Relay Marathon (NOI20_relaymarathon)	C++17	100 / 100	2931 ms	160400 KiB

RelayMarathon

#include <bits/stdc++.h>

using namespace std;

const long long MAX = 0x3f3f3f3f3f3f3f3f;

template<typename T>
bool minimize(T&x,T y) {
    return x > y ? x = y, true : false;
}

int buckSiz;
pair<long long, int> bucket[8];

struct FourMin {
    pair<long long, int> v[4];

    FourMin() {
        for (int i = 0; i < 4; ++i) {
            v[i] = make_pair(MAX, -1);
        }
    }

    FourMin operator + (long long x) const {
        FourMin tmp;
        for (int i = 0; i < 4; ++i) {
            if (v[i].second != -1) {
                tmp.v[i].first = v[i].first + x; 
                tmp.v[i].second = v[i].second;
            }
        }
        return tmp;
    }
    
    bool update(const FourMin& val) {
        buckSiz = 0;
        for (int i = 0; i < 4; ++i) {
            bucket[buckSiz++] = v[i];
            bucket[buckSiz++] = val.v[i];
        }
        sort(bucket, bucket+buckSiz);
        bool flag = false;
        int j = 0;
        for (int i = 0; i < buckSiz; ++i) {
            bool found = false;
            for (int k = 0; k < j; ++k) {
                if (v[k].second == bucket[i].second && bucket[i].second != -1) {
                    found = true;
                    break;
                }
            }
            if (!found) {
                flag |= v[j] > bucket[i];
                v[j++] = bucket[i];
                if (j == 4) {
                    break;
                }
            }
        }
        return flag;
    }

    void update(const pair<long long, int>& x) {
        buckSiz = 0;
        for (int i = 0; i < 4; ++i) {
            bucket[buckSiz++] = v[i];
        }
        bucket[buckSiz++] = x;
        sort(bucket,bucket+buckSiz);
        int j = 0;
        for (int i = 0; i < buckSiz; ++i) {
            bool found = false;
            for (int k = 0; k < j; ++k) {
                if (v[k].second == bucket[i].second && bucket[i].second != -1) {
                    found = true;
                    break;
                }
            }
            if (!found) {
                v[j++] = bucket[i];
                if (j == 4) {
                    break;
                }
            }
        }
    }

    bool operator < (const FourMin& val) const {
        for (int i = 0; i < 4; ++i) {
            if (v[i].first != val.v[i].first) {
                return v[i].first > val.v[i].first;
            }
        }
        return true;
    }

    bool operator != (const FourMin& val) const {
        for (int i = 0; i < 4; ++i) {
            if (v[i] != val.v[i]) {
                return true;
            }
        }
        return false;
    }

    friend ostream& operator << (ostream& os, const FourMin& val) {
        for (int i = 0; i < 4; ++i) {
            os << i << " -> " << val.v[i].first << ' ' << val.v[i].second << '\n';
            os << "------\n";
        }
        return os;
    }
};

const int N = 1e5+7;
int numNode, numEdge, numSpec;
vector<pair<int,int>> adj[N];
vector<int> specs;
FourMin dist[N];
long long res;
int src[2], snk[2];
int candSiz;
pair<long long, pair<int,int>> candidates[N*4];

void dijkstra() {
    priority_queue<pair<FourMin, int>> heap;
    for (int x : specs) {
        dist[x].v[0] = make_pair(0, x);
        heap.emplace(dist[x], x);
    }
    while (!heap.empty()) {
        int u = heap.top().second;
        FourMin w = heap.top().first;
        // cerr << " >> " << u << '\n';
        heap.pop();
        if (dist[u] != w) {
            continue;
        }
        for (pair<int,int> e : adj[u]) {
            int v = e.first;
            int w = e.second;
            // cerr << u << ": \n" << (dist[u]);
            // cerr << v << ": \n" << dist[v];
            if (dist[v].update(dist[u] + w)) {
                // cerr << v << ": \n" << dist[v];
                heap.emplace(dist[v], v);
            }
        }
    }
}

bool deepdiff(const pair<int,int>& a, const pair<int,int>& b) {
    return a.first != b.first && a.first != b.second && a.second != b.first && a.second != b.second;
}

void processCaseOne() {
    pair<int,int> clos = candidates[0].second;
    // cerr << " >> ";
    // cerr << clos.first << ' ' << clos.second << '\n';
    for (int i = 1; i < candSiz; ++i) {
        if (deepdiff(clos, candidates[i].second)) {
            res = candidates[0].first + candidates[i].first;
            src[0] = clos.first;
            snk[0] = clos.second;
            src[1] = candidates[i].second.first;
            snk[1] = candidates[i].second.second;
            return;
        }
    }
}

void updateResult(long long r, int _src1, int _snk1, int _src2, int _snk2) {
    if (minimize(res, r)) {
        src[0] = _src1;
        snk[0] = _snk1;
        src[1] = _src2;
        snk[1] = _snk2;
    }
}

void processCaseTwo() {
    int beg[2];
    beg[0] = candidates[0].second.first;
    beg[1] = candidates[0].second.second;
    FourMin fm[2];
    for (int i = 0; i < candSiz; ++i) {
        for (int j = 0; j < 2; ++j) {
            if (candidates[i].second.first == beg[j] && candidates[i].second.second != beg[!j]) {
                fm[j].update(make_pair(candidates[i].first, candidates[i].second.second));
            } else if (candidates[i].second.second == beg[j] && candidates[i].second.first != beg[!j]) {
                fm[j].update(make_pair(candidates[i].first, candidates[i].second.first));
            }
        }
    }
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 4; ++j) {
            if (fm[0].v[i].second != fm[1].v[j].second) {
                updateResult(fm[0].v[i].first+fm[1].v[j].first, beg[0], fm[0].v[i].second, beg[1], fm[1].v[j].second);
            }
        }
    }
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    cin >> numNode >> numEdge >> numSpec;
    for (int i = 0; i < numEdge; ++i) {
        int x, y, w;
        cin >> x >> y >> w;
        adj[x].emplace_back(y, w);
        adj[y].emplace_back(x, w);
    }
    for (int i = 0; i < numSpec; ++i) {
        int x;
        cin >> x;
        specs.push_back(x);
    }
    dijkstra();

    // for (int i = 1; i <= numNode; ++i) {
    //     for (int j = 0; j < 4; ++j) {
    //         cerr << i << " : " << j << " -> " << dist[i].v[j].first << ' ' << dist[i].v[j].second << '\n';
    //     }
    // }

    for (int i = 1; i <= numNode; ++i) {
        for (int j = 0; j < 4; ++j)
        for (int k = j+1; k < 4; ++k) {
            if (dist[i].v[j].second != -1 && dist[i].v[k].second != -1) {
                candidates[candSiz++] = make_pair(dist[i].v[j].first+dist[i].v[k].first, make_pair(dist[i].v[j].second, dist[i].v[k].second));
            }
        }
    }

    sort(candidates, candidates+candSiz);

    processCaseOne();
    processCaseTwo();

    cout << res;

    // for (int i = 0; i < 2; ++i) {
    //     cerr << " >>> " << src[i] << ' ' << snk[i] << '\n';
    // }

    return 0;
}

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