Submission #60909

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
60909	2018-07-25T00:51:49 Z	Benq	Commuter Pass (JOI18_commuter_pass)	C++11	100 / 100	762 ms	89196 KB

commuter_pass

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

int N,M,S,T,U,V;


template<int SZ> struct Dijkstra {
    ll dist[SZ];
    vpi adj[SZ];
    priority_queue<pl,vpl,greater<pl>> q;
    
    void addEdge(int A, int B, int C) {
        adj[A].pb({B,C}), adj[B].pb({A,C});
    }
    
    void gen(int st) {
        fill_n(dist,SZ,INF); 
        q = priority_queue<pl,vpl,greater<pl>>();
        
        dist[st] = 0; q.push({0,st});
    	while (sz(q)) {
    		pl x = q.top(); q.pop();
    		if (dist[x.s] < x.f) continue;
    		for (pi y: adj[x.s]) if (x.f+y.s < dist[y.f]) {
    			dist[y.f] = x.f+y.s;
    			q.push({dist[y.f],y.f});
    		}
    	}
    }
};

Dijkstra<MX> D;
ll dist[2][MX], DIST[2][MX];
pl mn[MX];
bool ok[MX];

pl comb(pl a, pl b) {
    return {min(a.f,b.f),min(a.s,b.s)};
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> M >> S >> T >> U >> V;
    F0R(i,M) {
        int A,B,C; cin >> A >> B >> C;
        D.addEdge(A,B,C);
    }
    
    D.gen(U);
    FOR(i,1,N+1) dist[0][i] = D.dist[i];
    D.gen(V);
    FOR(i,1,N+1) dist[1][i] = D.dist[i];
    
    FOR(i,1,N+1) mn[i] = {INF,INF};
    D.gen(S);
    FOR(i,1,N+1) DIST[0][i] = D.dist[i];
    D.gen(T);
    FOR(i,1,N+1) DIST[1][i] = D.dist[i];
    
    ll ans = dist[0][V];
    vpl v; 
    FOR(i,1,N+1) if (DIST[0][i]+DIST[1][i] == DIST[0][T]) {
        ok[i] = 1;
        v.pb({DIST[0][i],i});
    }
    sort(v.rbegin(),v.rend());
    for (auto a: v) {
        for (auto t: D.adj[a.s]) if (ok[t.f]) mn[a.s] = comb(mn[a.s],mn[t.f]);
        ans = min(ans,min(mn[a.s].f+dist[1][a.s],mn[a.s].s+dist[0][a.s]));
        mn[a.s] = comb(mn[a.s],{dist[0][a.s],dist[1][a.s]});
    }
    cout << ans;
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	536 ms	21548 KB	Output is correct
2	Correct	508 ms	23784 KB	Output is correct
3	Correct	728 ms	29756 KB	Output is correct
4	Correct	503 ms	31576 KB	Output is correct
5	Correct	582 ms	35468 KB	Output is correct
6	Correct	573 ms	38996 KB	Output is correct
7	Correct	536 ms	38996 KB	Output is correct
8	Correct	644 ms	38996 KB	Output is correct
9	Correct	553 ms	38996 KB	Output is correct
10	Correct	476 ms	38996 KB	Output is correct
11	Correct	288 ms	38996 KB	Output is correct
12	Correct	500 ms	38996 KB	Output is correct

Subtask #2
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	612 ms	38996 KB	Output is correct
2	Correct	637 ms	38996 KB	Output is correct
3	Correct	589 ms	38996 KB	Output is correct
4	Correct	562 ms	41276 KB	Output is correct
5	Correct	669 ms	45340 KB	Output is correct
6	Correct	589 ms	46588 KB	Output is correct
7	Correct	644 ms	47712 KB	Output is correct
8	Correct	617 ms	47712 KB	Output is correct
9	Correct	632 ms	47712 KB	Output is correct
10	Correct	762 ms	47712 KB	Output is correct
11	Correct	312 ms	47712 KB	Output is correct
12	Correct	651 ms	47712 KB	Output is correct

Subtask #3
24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	47712 KB	Output is correct
2	Correct	6 ms	47712 KB	Output is correct
3	Correct	8 ms	47712 KB	Output is correct
4	Correct	32 ms	47712 KB	Output is correct
5	Correct	21 ms	47712 KB	Output is correct
6	Correct	8 ms	47712 KB	Output is correct
7	Correct	8 ms	47712 KB	Output is correct
8	Correct	12 ms	47712 KB	Output is correct
9	Correct	9 ms	47712 KB	Output is correct
10	Correct	20 ms	47712 KB	Output is correct
11	Correct	7 ms	47712 KB	Output is correct
12	Correct	8 ms	47712 KB	Output is correct
13	Correct	7 ms	47712 KB	Output is correct
14	Correct	8 ms	47712 KB	Output is correct
15	Correct	8 ms	47712 KB	Output is correct

Subtask #4
45.0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	536 ms	21548 KB	Output is correct
2	Correct	508 ms	23784 KB	Output is correct
3	Correct	728 ms	29756 KB	Output is correct
4	Correct	503 ms	31576 KB	Output is correct
5	Correct	582 ms	35468 KB	Output is correct
6	Correct	573 ms	38996 KB	Output is correct
7	Correct	536 ms	38996 KB	Output is correct
8	Correct	644 ms	38996 KB	Output is correct
9	Correct	553 ms	38996 KB	Output is correct
10	Correct	476 ms	38996 KB	Output is correct
11	Correct	288 ms	38996 KB	Output is correct
12	Correct	500 ms	38996 KB	Output is correct
13	Correct	612 ms	38996 KB	Output is correct
14	Correct	637 ms	38996 KB	Output is correct
15	Correct	589 ms	38996 KB	Output is correct
16	Correct	562 ms	41276 KB	Output is correct
17	Correct	669 ms	45340 KB	Output is correct
18	Correct	589 ms	46588 KB	Output is correct
19	Correct	644 ms	47712 KB	Output is correct
20	Correct	617 ms	47712 KB	Output is correct
21	Correct	632 ms	47712 KB	Output is correct
22	Correct	762 ms	47712 KB	Output is correct
23	Correct	312 ms	47712 KB	Output is correct
24	Correct	651 ms	47712 KB	Output is correct
25	Correct	23 ms	47712 KB	Output is correct
26	Correct	6 ms	47712 KB	Output is correct
27	Correct	8 ms	47712 KB	Output is correct
28	Correct	32 ms	47712 KB	Output is correct
29	Correct	21 ms	47712 KB	Output is correct
30	Correct	8 ms	47712 KB	Output is correct
31	Correct	8 ms	47712 KB	Output is correct
32	Correct	12 ms	47712 KB	Output is correct
33	Correct	9 ms	47712 KB	Output is correct
34	Correct	20 ms	47712 KB	Output is correct
35	Correct	7 ms	47712 KB	Output is correct
36	Correct	8 ms	47712 KB	Output is correct
37	Correct	7 ms	47712 KB	Output is correct
38	Correct	8 ms	47712 KB	Output is correct
39	Correct	8 ms	47712 KB	Output is correct
40	Correct	581 ms	52680 KB	Output is correct
41	Correct	565 ms	55716 KB	Output is correct
42	Correct	564 ms	59960 KB	Output is correct
43	Correct	284 ms	59960 KB	Output is correct
44	Correct	342 ms	61276 KB	Output is correct
45	Correct	597 ms	69980 KB	Output is correct
46	Correct	493 ms	73032 KB	Output is correct
47	Correct	504 ms	75884 KB	Output is correct
48	Correct	355 ms	75884 KB	Output is correct
49	Correct	467 ms	81248 KB	Output is correct
50	Correct	549 ms	85460 KB	Output is correct
51	Correct	573 ms	89196 KB	Output is correct

Submission #60909

Compilation message

Subtask #1 16.0 / 16.0

Subtask #2 15.0 / 15.0

Subtask #3 24.0 / 24.0

Subtask #4 45.0 / 45.0

Subtask #1
16.0 / 16.0

Subtask #2
15.0 / 15.0

Subtask #3
24.0 / 24.0

Subtask #4
45.0 / 45.0