oj.uz

Submission #45643

# Submission time Handle Problem Language Result Execution time Memory
45643 2018-04-15T17:04:05 Z reality Commuter Pass (JOI18_commuter_pass) C++17
31 / 100
 735 ms 85764 KB 
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int N = (int)(1e6) + 5;
ll D1[N];
ll D2[N];
ll D3[N];
ll D4[N];
vector < pii > g[N];
int n;
void Go(ll D[],int S) {
	for (int i = 1;i <= n;++i)
		D[i] = 1e18;
	D[S] = 0;
	priority_queue < pair < ll , int > , vector < pair < ll , int > > , greater < pair < ll , int > > > Q;
	Q.push(mp(0,S));
	while (!Q.empty()) {
		const ll cost = Q.top().fi;
		const int node = Q.top().se;
		Q.pop();
		if (cost != D[node])
			continue;
		for (auto it : g[node])
			if (D[it.fi] > D[node] + it.se)
				D[it.fi] = D[node] + it.se,Q.push(mp(D[it.fi],it.fi));
	}
}
ll ans = 1e18;
vi order;
vi G[2][N];
int was[N];
void go(ll d1[],ll d2[],int who) {
	static ll D[N];
	for (int i = 1;i <= n;++i)
		D[i] = d1[i];
	for (auto u : order)
		for (auto v : G[who][u])
			smin(D[u],D[v]);
	for (int i = 1;i <= n;++i)
		smin(ans,D[i] + d2[i]);
}
int main(void)
{
    int m;
    int S,T,U,V;
    cin>>n>>m>>S>>T>>U>>V;
    while (m --) {
    	int a,b,c;
    	cin>>a>>b>>c;
    	g[a].pb(mp(b,c));
    	g[b].pb(mp(a,c));
    }
    Go(D1,S);
    Go(D2,T);
    Go(D3,U);
    Go(D4,V);
    queue < int > q;
    q.push(S);
    was[S] = 1;
    const ll dist = D1[T];
    while (!q.empty()) {
    	int node = q.front();
    	q.pop();
    	order.pb(node);
    	for (auto it : g[node])
    		if (D1[node] + it.se + D2[it.fi] == dist) {
    			if (!was[it.fi])
	    			was[it.fi] = 1,q.push(it.fi);
    		}
    }
    for (int i = 1;i <= n;++i) {
    	for (auto it : g[i]) {
    		if (D1[i] + it.se + D2[it.fi] == dist)
    			G[0][i].pb(it.fi);
    		if (D1[it.fi] + it.se + D2[i] == dist)
    			G[1][it.fi].pb(i);
    	}
    }
    ans = D3[V];
    for (int cs = 0;cs < 2;++cs) {
	    go(D3,D4,cs);
	    go(D4,D3,cs);
	    reverse(all(order));
	    go(D3,D4,cs);
	    go(D4,D3,cs);
	    reverse(all(order));
	}
    cout << ans << '\n';
    return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 636 ms 83528 KB Output is correct
2 Correct 625 ms 83528 KB Output is correct
3 Correct 692 ms 85656 KB Output is correct
4 Correct 713 ms 85656 KB Output is correct
5 Correct 692 ms 85656 KB Output is correct
6 Correct 697 ms 85656 KB Output is correct
7 Correct 685 ms 85656 KB Output is correct
8 Correct 647 ms 85656 KB Output is correct
9 Correct 661 ms 85656 KB Output is correct
10 Correct 588 ms 85656 KB Output is correct
11 Correct 327 ms 85656 KB Output is correct
12 Correct 682 ms 85656 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 735 ms 85656 KB Output is correct
2 Correct 654 ms 85656 KB Output is correct
3 Correct 708 ms 85656 KB Output is correct
4 Correct 689 ms 85656 KB Output is correct
5 Correct 670 ms 85656 KB Output is correct
6 Correct 670 ms 85656 KB Output is correct
7 Correct 727 ms 85764 KB Output is correct
8 Correct 678 ms 85764 KB Output is correct
9 Correct 632 ms 85764 KB Output is correct
10 Correct 686 ms 85764 KB Output is correct
11 Correct 322 ms 85764 KB Output is correct
12 Correct 661 ms 85764 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 85764 KB Output is correct
2 Correct 59 ms 85764 KB Output is correct
3 Correct 61 ms 85764 KB Output is correct
4 Correct 117 ms 85764 KB Output is correct
5 Correct 84 ms 85764 KB Output is correct
6 Correct 69 ms 85764 KB Output is correct
7 Correct 69 ms 85764 KB Output is correct
8 Correct 64 ms 85764 KB Output is correct
9 Incorrect 61 ms 85764 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 636 ms 83528 KB Output is correct
2 Correct 625 ms 83528 KB Output is correct
3 Correct 692 ms 85656 KB Output is correct
4 Correct 713 ms 85656 KB Output is correct
5 Correct 692 ms 85656 KB Output is correct
6 Correct 697 ms 85656 KB Output is correct
7 Correct 685 ms 85656 KB Output is correct
8 Correct 647 ms 85656 KB Output is correct
9 Correct 661 ms 85656 KB Output is correct
10 Correct 588 ms 85656 KB Output is correct
11 Correct 327 ms 85656 KB Output is correct
12 Correct 682 ms 85656 KB Output is correct
13 Correct 735 ms 85656 KB Output is correct
14 Correct 654 ms 85656 KB Output is correct
15 Correct 708 ms 85656 KB Output is correct
16 Correct 689 ms 85656 KB Output is correct
17 Correct 670 ms 85656 KB Output is correct
18 Correct 670 ms 85656 KB Output is correct
19 Correct 727 ms 85764 KB Output is correct
20 Correct 678 ms 85764 KB Output is correct
21 Correct 632 ms 85764 KB Output is correct
22 Correct 686 ms 85764 KB Output is correct
23 Correct 322 ms 85764 KB Output is correct
24 Correct 661 ms 85764 KB Output is correct
25 Correct 84 ms 85764 KB Output is correct
26 Correct 59 ms 85764 KB Output is correct
27 Correct 61 ms 85764 KB Output is correct
28 Correct 117 ms 85764 KB Output is correct
29 Correct 84 ms 85764 KB Output is correct
30 Correct 69 ms 85764 KB Output is correct
31 Correct 69 ms 85764 KB Output is correct
32 Correct 64 ms 85764 KB Output is correct
33 Incorrect 61 ms 85764 KB Output isn't correct
34 Halted 0 ms 0 KB -