Submission #633566

#	Time	Username	Problem	Language	Result	Execution time	Memory
633566		kobebryan9	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	471 ms	49004 KiB

commuter_pass

//https://play.google.com/store/apps/details?id=prod.com.pingidentity.pingid
#pragma GCC optimize("O3,no-stack-protector,unroll-loops,fast-math")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define lim 10000005
#define kk 1000000007
#define INF 1e16
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define sz(x) x.size()
#define vl vector<ll>
#define bug printf("Yes %d\n", tmp)
#define enter printf("\n")
#define space printf(" ")
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << endl;
	err(++it, args...);
}

struct yo
{
    ll x, y, w;
    bool operator <(const yo &t) const
    {
        return w < t.w;
    }
}edge[200005];

template <typename D>
void put(vector<D> aa,int st, int ed)
{
    for (int i = st; i < ed; i++)
    {
        cout << aa[i] << " ";
    }
    cout << aa[ed] << endl;
}

#define mod (int)(1e9 + 7)
ll bg(ll x, ll y)
{ // big mod
    if (y == 1)
        return x % mod;
    else if (y % 2 == 0)
    {
        ll tmp = bg(x, y / 2);
        return ((tmp % mod) * tmp) % mod;
    }
    else
        return (bg(x, y - 1) * x) % mod;
}

typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> Multi_Set;
// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> Multi_Set; -> normal set // can change to multi_set by pair<int , occ[int]>
//*find_by_order(), order_of_key()

template <typename T = int>
class bit
{
private:
    vector<T> a;

public:
    bit(int n) { a.resize(n + 1); }

    void add(int i, T x)
    {
        for (; i < a.size(); i += i & -i)
            a[i] += x;
    }

    T sum(int i)
    {
        T ans = 0;
        for (; i > 0; i -= i & -i)
            ans += a[i];
        return ans;
    }

    void clear() { a.assign(a.size(), 0); }
};
// bit<ll > b2(300);

vl fac, inv, numinv; // ncr and fac

inline ll ncr(int n, int r)
{
    if (n < 0 || r < 0 || r > n)
        return 0;
    return fac[n] * inv[r] % mod * inv[n - r] % mod;
}
inline void calfacinv(int n)
{
    fac.reserve(n + 1);
    fac[0] = fac[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        fac[i] = fac[i - 1] * i % mod;
    }
    numinv.reserve(n + 1);
    numinv[0] = numinv[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        numinv[i] = numinv[mod % i] * (mod - mod / i) % mod;
    }
    inv.reserve(n + 1);
    inv[0] = inv[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        inv[i] = numinv[i] * inv[i - 1] % mod;
    }
    return;
}

/* SOS DP
for(int i = 0;i < N; ++i) for(int mask = 0; mask < (1<<N); ++mask){ //order is not important
    if(mask & (1<<i))
        F[mask] += F[mask^(1<<i)];
}
*/
// ll rectsum(int x,int y,int xx,int yy){
//   if (y > yy || x > xx) return 0;
//   return psum[xx][yy] - psum[xx][y-1] - psum[x-1][yy] + psum[x-1][y-1];
// }

ll bt(ll x){
    return (1<<x);
}

ll t, n, m, k, ans, l, r, mi, tot, cnt, q, c, S, T, U, V;
string ss1, ss2, ss[505];
vector<ll> ee[300005];
vector<pair<ll, ll> > ee2[300005], ee3[300005];
int cycle = 0;

ll cost(pair<ll, ll> a, pair<ll, ll> b){
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
    //return (abs(a.x - b.x) + abs(a.y - b.y)) * (abs(a.x - b.x) + abs(a.y - b.y));
}

vector<ll> sp1(200005, INF), sp2(200005, INF), sp3(200005, INF), sp5(200005, INF);

void dijk(int st, vector<ll>& sp, vector<pair<ll, ll>> adj[]){

    sp[st] = 0;
    priority_queue<pair<ll, ll>> q;
    vector<int> vis(n+5);
    q.push({0,st});
    while (!q.empty()){
        ll len = -q.top().x;
        ll x = q.top().y;
        q.pop();
        if (sp[x] != len || vis[x] == 1) continue;
        vis[x] = 1;
        for (auto u: adj[x]){
            //if (u.x == n) continue;
            if (sp[u.x] > len + u.y){
                sp[u.x] = len + u.y;
                q.push({-sp[u.x],u.x});
            }
        }
    }
}

void dijk2(int st, vector<pair<ll, ll>> adj[], int ed, int ed2){
    
    vector<ll> sp4(200005, INF);

    priority_queue<pair<ll, ll>> q;
    vector<ll> sp(n+5, INF);
    vector<int> vis(n+5);
    sp[st] = 0;
    q.push({0,st});

    if (ed == U) sp4[st] = sp1[st];
    if (ed == V) sp4[st] = sp2[st];

    while (!q.empty()){
        ll len = -q.top().x;
        ll x = q.top().y;
        q.pop();
        if (sp[x] != len || vis[x] == 1) continue;
        vis[x] = 1;
        if (sp3[x] + sp5[x] == sp5[S]){ // this is one of the station that can buy pass
            ll tmp1, tmp2;
            if (ed == U){
                tmp1 = sp1[x];
                tmp2 = sp2[x];
            }else{
                tmp2 = sp1[x];
                tmp1 = sp2[x];
            }
            sp4[x] = min(sp4[x], tmp1);
            ans = min(ans, sp4[x] + tmp2);
        }
        for (auto u: adj[x]){
            //if (u.x == n) continue;
            if (sp[u.x] > len + u.y){
                sp[u.x] = len + u.y;
                q.push({-sp[u.x],u.x});
            }
            if (sp3[u.x] == len + u.y){
                sp4[u.x] = min(sp4[u.x], sp4[x]);
            }
        }
    }
    // for (int i=1;i<=n;i++){
    //     error(i, sp4[i])
    // }
}


void solve(){
    ios::sync_with_stdio(false), cin.tie(0);
    // freopen("dining.in","r",stdin);
    // freopen("dining.out","w",stdout);  
    //set<ll> ss;
    cin >> n >> m >> S >> T >> U >> V;

    map<int, int> mm;
    //pair<ll, ll> hh[100005];

    //vector<int> cc(n+5), dd(n+5), lis;
    //vector<vector<int>> cc(n+5, vector<int> (n+5)), dd(n+5, vector<int> (n+5));

    //vector<vector<ll>> dp(bt(n), vector<ll> (n+5, 0));
    //vector<vector<ll>> dp(n+5, vector<ll> (n+5,  0));

    for (int i=0;i<m;i++){
        ll x, y, w;
        cin >> x >> y >> w;
        edge[i] = {x,y,w};
        ee2[x].pb({y,w});
        ee2[y].pb({x,w});
    }

    dijk(U, sp1, ee2);
    dijk(V, sp2, ee2);
    dijk(S, sp3, ee2);
    dijk(T, sp5, ee2);

    ans = sp1[V];
    error(ans)

    dijk2(S, ee2, U, V);
    dijk2(S, ee2, V, U);

    //cout << sp1[n] << " " << sp2[n] << " " << sp4[n] << " " << sp3[n] << endl;
    cout << ans << endl;
    //vector<vector<ll>> cc(n+5, vector<ll> (n+5, 0));

    //dp[0][0] = 0;
    //ll tot = 0;
    //ll ans = 0;
    vector<ll> tmp;

    //sort(hh+1, hh+n+1);
    //vector<vector<vector<ll>>> dp(n + 5, vector<vector<ll>> (m + 5, vector<ll> (2, 1e16)));


    //cout << dp[n][m][0] << endl;
    // vector<vector<ll>> dp(n+5, vector<ll>(n+5, kk));
    // dp[0][0] = 0;
    //vector<ll> dp();

    //cout << ans << endl;
    return;
    // for (int i=0;i<n;i++){
    //     if (i == n-1) cout << cc[i] << endl;
    //     else cout << cc[i] << " ";
    // }
    
    // if (ans) cout << "YES" << endl;
    // else cout << "NO" << endl;
    //		for (int i=1;i<=n;i++) cc[i] = 0;
    //		for (int i=1;i<=n;i++) printf("%d ",dd[i]);
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    t = 1;
    //cin >> t;
    while (t--){
        solve();
    }
}
/*
*/

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