oj.uz

Submission #379566

# Submission time Handle Problem Language Result Execution time Memory
379566 2021-03-18T15:56:05 Z leu_naut Commuter Pass (JOI18_commuter_pass) C++11
100 / 100
 709 ms 37112 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
#define FOR(i,a,b) for (int i = a; i <= b; ++i)
#define FORd(i,a,b) for (int i = a;i >= b; --i)
#define pii pair<ll,ll>
#define FastRead ios_base::sync_with_stdio(0); cin.tie(nullptr);
 
const int N = 2e5 + 10;
const ll oo = 1e18;
const int MOD = 1e9 + 7;
 
vector <pii> g[N + 10];
ll n,m,s,t,u,v,ans = oo;
ll vs[N + 10],dp[2][N + 10],du[N + 10],dv[N + 10],ds[N + 10];
 
void dijsktra1(int x, ll arr[])
{
    memset(vs,false,sizeof(vs));
   	priority_queue <pii> pq;
   	pq.push({0,x});
    while (!pq.empty()) {
        ll c,node;
        tie(c,node) = pq.top();
        pq.pop();
        if (!vs[node]) {
            vs[node] = true;
            arr[node] = -c;
            for (pii i : g[node]) pq.push(pii(c - i.first,i.second));
        }
    }
}
 
void dijsktra2(ll x, ll y)
{
    fill(dp[0], dp[0] + N, oo);
    fill(dp[1], dp[1] + N, oo);
    memset(vs,false,sizeof(vs));
    priority_queue <pair <ll,pair <ll,ll>>> pq;
    pq.push(make_pair(0ll,pii(x,0ll)));
    while (!pq.empty()) {
        ll c,node,par; pii p;
        tie(c,p) = pq.top();
        tie(node,par) = p;
        pq.pop();
        if (!vs[node]) {
            vs[node] = true;
            ds[node] = -c;
            dp[0][node] = min(du[node], dp[0][par]);
            dp[1][node] = min(dv[node], dp[1][par]);
            for (pii i : g[node]) pq.push(make_pair(c - i.first,pii(i.second,node)));
        }
        else if (-c == ds[node]) {
			ll so = min(du[node],dp[0][par]), so2 = min(dv[node],dp[1][par]);
			if (so + so2 <= dp[0][node] + dp[1][node]) {
			dp[0][node] = min({du[node], dp[0][par]});
            dp[1][node] = min({dv[node], dp[1][par]});
			}
        }
    }
	ans = min(ans,dp[0][y] + dp[1][y]);
}
 
int main()
{
	FastRead
	cin >> n >> m >> s >> t >> u >> v;
	FOR(i,1,m) {
		int u,v,w;
		cin >> u >> v >> w;
		g[u].push_back(pii(w,v));
        g[v].push_back(pii(w,u));
	}
	dijsktra1(u,du);
	dijsktra1(v,dv);	
	ans = du[v];
	dijsktra2(s,t);
    dijsktra2(t,s);
	cout << ans;	
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 709 ms 36608 KB Output is correct
2 Correct 613 ms 36024 KB Output is correct
3 Correct 604 ms 35640 KB Output is correct
4 Correct 679 ms 35744 KB Output is correct
5 Correct 583 ms 32072 KB Output is correct
6 Correct 699 ms 36564 KB Output is correct
7 Correct 599 ms 35584 KB Output is correct
8 Correct 590 ms 35728 KB Output is correct
9 Correct 669 ms 36928 KB Output is correct
10 Correct 624 ms 37056 KB Output is correct
11 Correct 183 ms 19436 KB Output is correct
12 Correct 655 ms 37112 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 621 ms 36076 KB Output is correct
2 Correct 594 ms 32088 KB Output is correct
3 Correct 636 ms 35548 KB Output is correct
4 Correct 587 ms 32220 KB Output is correct
5 Correct 610 ms 31868 KB Output is correct
6 Correct 612 ms 35516 KB Output is correct
7 Correct 619 ms 32076 KB Output is correct
8 Correct 557 ms 32132 KB Output is correct
9 Correct 589 ms 31888 KB Output is correct
10 Correct 577 ms 35328 KB Output is correct
11 Correct 173 ms 19436 KB Output is correct
12 Correct 616 ms 35496 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 12924 KB Output is correct
2 Correct 8 ms 9836 KB Output is correct
3 Correct 8 ms 9836 KB Output is correct
4 Correct 91 ms 16176 KB Output is correct
5 Correct 57 ms 13864 KB Output is correct
6 Correct 9 ms 9964 KB Output is correct
7 Correct 13 ms 10092 KB Output is correct
8 Correct 13 ms 10220 KB Output is correct
9 Correct 9 ms 9964 KB Output is correct
10 Correct 46 ms 13852 KB Output is correct
11 Correct 7 ms 9836 KB Output is correct
12 Correct 7 ms 9836 KB Output is correct
13 Correct 9 ms 9836 KB Output is correct
14 Correct 9 ms 9836 KB Output is correct
15 Correct 8 ms 9964 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 709 ms 36608 KB Output is correct
2 Correct 613 ms 36024 KB Output is correct
3 Correct 604 ms 35640 KB Output is correct
4 Correct 679 ms 35744 KB Output is correct
5 Correct 583 ms 32072 KB Output is correct
6 Correct 699 ms 36564 KB Output is correct
7 Correct 599 ms 35584 KB Output is correct
8 Correct 590 ms 35728 KB Output is correct
9 Correct 669 ms 36928 KB Output is correct
10 Correct 624 ms 37056 KB Output is correct
11 Correct 183 ms 19436 KB Output is correct
12 Correct 655 ms 37112 KB Output is correct
13 Correct 621 ms 36076 KB Output is correct
14 Correct 594 ms 32088 KB Output is correct
15 Correct 636 ms 35548 KB Output is correct
16 Correct 587 ms 32220 KB Output is correct
17 Correct 610 ms 31868 KB Output is correct
18 Correct 612 ms 35516 KB Output is correct
19 Correct 619 ms 32076 KB Output is correct
20 Correct 557 ms 32132 KB Output is correct
21 Correct 589 ms 31888 KB Output is correct
22 Correct 577 ms 35328 KB Output is correct
23 Correct 173 ms 19436 KB Output is correct
24 Correct 616 ms 35496 KB Output is correct
25 Correct 49 ms 12924 KB Output is correct
26 Correct 8 ms 9836 KB Output is correct
27 Correct 8 ms 9836 KB Output is correct
28 Correct 91 ms 16176 KB Output is correct
29 Correct 57 ms 13864 KB Output is correct
30 Correct 9 ms 9964 KB Output is correct
31 Correct 13 ms 10092 KB Output is correct
32 Correct 13 ms 10220 KB Output is correct
33 Correct 9 ms 9964 KB Output is correct
34 Correct 46 ms 13852 KB Output is correct
35 Correct 7 ms 9836 KB Output is correct
36 Correct 7 ms 9836 KB Output is correct
37 Correct 9 ms 9836 KB Output is correct
38 Correct 9 ms 9836 KB Output is correct
39 Correct 8 ms 9964 KB Output is correct
40 Correct 642 ms 36456 KB Output is correct
41 Correct 668 ms 36848 KB Output is correct
42 Correct 668 ms 36932 KB Output is correct
43 Correct 179 ms 19436 KB Output is correct
44 Correct 190 ms 19436 KB Output is correct
45 Correct 584 ms 30888 KB Output is correct
46 Correct 586 ms 30472 KB Output is correct
47 Correct 658 ms 32124 KB Output is correct
48 Correct 187 ms 19180 KB Output is correct
49 Correct 643 ms 34880 KB Output is correct
50 Correct 562 ms 30644 KB Output is correct
51 Correct 577 ms 30620 KB Output is correct