Submission #381775

#	Time	Username	Problem	Language	Result	Execution time	Memory
381775		oleksg	Commuter Pass (JOI18_commuter_pass)	C++11	100 / 100	629 ms	40032 KiB

commuter_pass

#pragma GCC optimize("O2")
#include <fstream>
#include <string>
#include <iostream>
#include <bitset>
#include <math.h>
#include <string>
#include <algorithm>
#include <assert.h>
#include <bits/stdc++.h>
#include <vector>
#include <queue>
#include<stdio.h>
#include<ctype.h>
#define ll long long
using namespace std;

struct con{
    ll des;
    ll w;
};

ll n, m;

ll s, t;

ll u, v;

ll dist[100001];
ll used[100001];


ll dpfu[100001];
ll dpbv[100001];

ll used2[100001];
ll dist2[100001];
ll keep[100001];
ll answer = 1e15;
// keep track of all the nodes going to us that can reach us in the minimum distance, later updated to only be nodes that go to us however we also gotta be a usable node that leads back to t
vector<ll> tous[100001];


vector<con> cons[100001];

vector<ll> freeconsfor[100001];
vector<ll> freeconsback[100001];

void dfsdp(ll cur, ll arr[], ll dis[], bool bck){
    used[cur] = 1;
    if (bck){
        arr[cur] = dis[cur];
        for(auto next:freeconsback[cur]){
            if (used[next] == 0){
                used[next] = 1;
                dfsdp(next, arr, dis, bck);
            }
            arr[cur] = min(arr[cur], arr[next]);
        }
    }
    else{
        arr[cur] = dis[cur];
        for(auto next:freeconsfor[cur]){
            if (used[next] == 0){
                used[next] = 1;
                dfsdp(next, arr, dis, bck);
            }
            arr[cur] = min(arr[cur], arr[next]);
        }
    }
}
void dpprocess(){
    for (int x = 0; x < n; x++){
        used[x] = 0;
        dpfu[x] = 1e15;
        dpbv[x] = 1e15;
    }
    dfsdp(t, dpfu, dist, true);
    for (int x = 0; x < n; x++){
        used[x] = 0;
    }
    dfsdp(s, dpbv, dist2, false);
}
struct node{
    ll dist;
    ll cur;
    ll dir;
};

bool Compare(node a, node b)
{
    return a.dist > b.dist;
}

void dfs(int cur){
    keep[cur] = 1;
    for (auto it: tous[cur]){
        if (keep[it] == -1){
            keep[it] = 1;
            dfs(it);
        }
    }
}
int main(){
    /*201503963*/
    //ifstream in("03-07.txt");
    cin >> n >> m >> s >> t >> u >> v;
    s -= 1;
    t -= 1;
    u -= 1;
    v -= 1;
    ll one, two, three;
    for (int x = 0; x < m; x++){
        cin >> one >> two >> three;
        cons[one - 1].push_back({two - 1, three});
        cons[two - 1].push_back({one - 1, three});
    }
    for (int x = 0; x < n; x++){
        dist[x] = 1e15;
        used[x] = -1;
        keep[x] = -1;
    }
    priority_queue<pair<ll, ll>> q;
    dist[s] = 0;
    q.push({0, s});
    while(q.size() > 0){
        ll curdist = q.top().first * -1;
        ll cur = q.top().second;
        q.pop();
        if (used[cur] == -1){
            used[cur] = 1;
            for (auto next: cons[cur]){
                if (dist[next.des] > dist[cur] + next.w){
                    dist[next.des] = dist[cur] + next.w;
                    tous[next.des].clear();
                    tous[next.des].push_back(cur);
                    q.push({-1*dist[next.des], next.des});
                }
                else if (dist[next.des] == dist[cur] + next.w){
                    //partial update
                    tous[next.des].push_back(cur);
                }
            }
        }
    }
    dfs(t);
    for (int x = 0; x < n; x++){
        if (keep[x] == 1){
            for (auto it: tous[x]){
                //cout << x << " " << it << "\n";
                freeconsback[x].push_back(it);
                freeconsfor[it].push_back(x);
                //cout << x << " " << it << " " << "free\n";
            }
        }
    }
    //cout << keep[s] << " " << freeconsfor[s].size() << "\n";
    //dijkstra part 2, this time we know what the free cons are
    for (int x = 0; x < n; x++){
        dist[x]= 1e15;
        used[x] = -1;
    }
    q.push({0, u});
    dist[u] = 0;
    while(q.size() > 0){
        ll curdist = q.top().first * -1;
        ll cur = q.top().second;
        q.pop();
        if (used[cur] == -1){
            used[cur] = 1;
            for (auto next: cons[cur]){
                if (dist[next.des] > dist[cur] + next.w){
                    dist[next.des] = dist[cur] + next.w;

                    q.push({-1*dist[next.des], next.des});
                }
            }
        }
    }
    for (int x = 0; x < n; x++){
        dist2[x]= 1e15;
        used2[x] = -1;
    }
    q.push({0, v});
    dist2[v] = 0;
    while(q.size() > 0){
        ll curdist = q.top().first * -1;
        ll cur = q.top().second;
        q.pop();
        if (used2[cur] == -1){
            used2[cur] = 1;
            for (auto next: cons[cur]){
                if (dist2[next.des] > dist2[cur] + next.w){
                    dist2[next.des] = dist2[cur] + next.w;

                    q.push({-1*dist2[next.des], next.des});
                }
            }
        }
    }
    dpprocess();
    for (int x = 0; x < n; x++){
        answer = min(dpfu[x] + dpbv[x], answer);
    }
    swap(v, u);
    for (int x = 0; x < n; x++){
        ll sw = dist2[x];
        dist2[x] = dist[x];
        dist[x] = sw;
    }
    dpprocess();
    for (int x = 0; x < n; x++){
        answer = min(dpfu[x] + dpbv[x], answer);
    }
    cout << min(answer, dist2[u]) << "\n";

}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:127:12: warning: unused variable 'curdist' [-Wunused-variable]
  127 |         ll curdist = q.top().first * -1;
      |            ^~~~~~~
commuter_pass.cpp:166:12: warning: unused variable 'curdist' [-Wunused-variable]
  166 |         ll curdist = q.top().first * -1;
      |            ^~~~~~~
commuter_pass.cpp:187:12: warning: unused variable 'curdist' [-Wunused-variable]
  187 |         ll curdist = q.top().first * -1;
      |            ^~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45