Submission #1216491

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216491		InvMOD	Relay Marathon (NOI20_relaymarathon)	C++20	100 / 100	1417 ms	80848 KiB

RelayMarathon

#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define all(v) (v).begin(), (v).end()

template<typename T> bool ckmn(T& a, const T& b){
    if(a > b)
        return a = b, true;
    return false;
}

const int N = 1e5 + 5, M = 3e6 + 5, INF = 1e9;

/*
    minimum distance = (a,b)
    {x1, y1} != (a) and (b) -> optimal to choose (a,b)
    {(a), y1} != (b) -> if we choose {x2, y2} != (a) and (b) we should choose (a,b)
                     -> we have to choose {(b), y2}
*/

struct Edge{
    int u,v,w;
    Edge(int u = 0, int v = 0, int w = 0): u(u), v(v), w(w) {}
};

int n, m, k, dist[N], near[N];

bool special[N]; Edge E[M];

vector<int> adj[N];

void dijkstra(){
    priority_queue<pair<int,int>> pq;

    for(int i = 1; i <= n; i++){
        if(special[i]) pq.push(make_pair(0, i));
    }

    while(!pq.empty()){
        pair<int,int> e = pq.top(); pq.pop();

        int x = e.second, cur_dist = -e.first;
        if(cur_dist > dist[x]) continue;

        for(int id : adj[x]){
            int v = E[id].u ^ E[id].v ^ x, w = E[id].w;
            if(ckmn(dist[v], dist[x] + w)){
                near[v] = near[x];
                pq.push(make_pair(-dist[v], v));
            }
        }
    }
}

void solve()
{
    cin >> n >> m >> k;
    for(int i = 0; i < m; i++){
        int u,v,w; cin >> u >> v >> w;
        E[i] = Edge(u, v, w);
        adj[u].pb(i), adj[v].pb(i);
    }

    for(int i = 0; i < k; i++){
        int x; cin >> x;
        special[x] = true;
    }

    auto reset = [&]() -> void{
        for(int i = 1; i <= n; i++){
            if(special[i]) dist[i] = 0, near[i] = i;
            else dist[i] = INF, near[i] = 0;
        }
    };
    reset(), dijkstra();


    int opt1 = -1, opt2 = -1, cdist = INF;
    for(int i = 0; i < m; i++){
        int u = E[i].u, v = E[i].v, w = E[i].w;
        if(near[u] == near[v]) continue;
        if(ckmn(cdist, dist[u] + dist[v] + w)){
            opt1 = near[u];
            opt2 = near[v];
        }
    }

    special[opt1] = special[opt2] = false;
//    cout << "FOUND OPT: " << opt1 <<" " << opt2 << "\n";

    reset(), dijkstra();

    int answer = INF;
    for(int i = 0; i < m; i++){
        int u = E[i].u, v = E[i].v, w = E[i].w;
        if(near[u] == near[v]) continue;
        ckmn(answer, cdist + dist[u] + dist[v] + w);
    }

    vector<int> MnOpt1(n + 1, INF);

    special[opt1] = true; reset(), dijkstra();
    for(int i = 0; i < m; i++){
        int u = E[i].u, v = E[i].v, w = E[i].w;
        if(near[u] == near[v]) continue;

        if(near[u] == opt1 || near[v] == opt1){
            int target = (near[u] == opt1 ? near[v] : near[u]);
            ckmn(MnOpt1[target], dist[u] + dist[v] + w);
        }
    }
    special[opt1] = false;

    vector<int> MnOpt2(n + 1, INF);

    special[opt2] = true; reset(), dijkstra();
    for(int i = 0; i < m; i++){
        int u = E[i].u, v = E[i].v, w = E[i].w;
        if(near[u] == near[v]) continue;

        if(near[u] == opt2 || near[v] == opt2){
            int target = (near[u] == opt2 ? near[v] : near[u]);
            ckmn(MnOpt2[target], dist[u] + dist[v] + w);
        }
    }

    vector<int> idx1(n + 1, 0), idx2(n + 1, 0);
    for(int i = 1; i <= n; i++) idx1[i] = idx2[i] = i;

    sort(1 + all(idx1), [&](int x, int y){return MnOpt1[x] < MnOpt1[y];});
    sort(1 + all(idx2), [&](int x, int y){return MnOpt2[x] < MnOpt2[y];});

    int last_dist1 = MnOpt1[idx1[1]] + MnOpt2[(idx1[1] == idx2[1] ? idx2[2] : idx2[1])];
    int last_dist2 = MnOpt2[idx2[1]] + MnOpt1[(idx2[1] == idx1[1] ? idx1[2] : idx1[1])];

    answer = min(answer, min(last_dist1, last_dist2));
    cout << answer << "\n";
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP", "r", stdin);
        freopen(name".OUT", "w", stdout);
    }

    solve();
    return 0;
}

Compilation message (stderr)

RelayMarathon.cpp: In function 'int32_t main()':
RelayMarathon.cpp:148:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |         freopen(name".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
RelayMarathon.cpp:149:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |         freopen(name".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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