oj.uz

Submission #210604

# Submission time Handle Problem Language Result Execution time Memory
210604 2020-03-17T20:27:05 Z amiratou Commuter Pass (JOI18_commuter_pass) C++14
100 / 100
 495 ms 21428 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define rando mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define fi first
#define se second
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define debugii(x) cerr << " - " << #x << ": " << x.fi<<","<<x.se << endl;
#define sep() cerr << "--------------------" << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ld long double
#define ll long long
#define int ll
#define ii pair<int,int>
#define v vector<int>
#define vii vector<ii>
#define vv vector<vector<ii> >
#define mp make_pair
#define INF 1e15
#define pb push_back
#define EPS 1e-9
const int MOD = 1000000007; // 998244353
int dist[6][100005];//1,n,U,V
int D[301][301];
int n,m,a,b,c;
vv vec;
void sssp(int node,int idx){
	for (int i = 0; i < n; ++i)
		dist[idx][i]=INF;
	dist[idx][node]=0;
	priority_queue<ii,vii,greater<ii> > pq;
	pq.push(ii(0,node));
	while(!pq.empty()){
		ii f=pq.top();
		pq.pop();
		if(dist[idx][f.se]<f.fi)
			continue;
		for(auto it:vec[f.se])
			if(dist[idx][it.fi]>(f.fi+it.se))
				dist[idx][it.fi]=f.fi+it.se,pq.push(ii(dist[idx][it.fi],it.fi));
	}
}
int32_t main(){
	boost;
	//freopen(".in","r",stdin);
	cin>>n>>m;
	int S,T,U,V;
	cin>>S>>T>>U>>V;
	S--,T--,U--,V--;
	vec.resize(n);
	while(m--){
		cin>>a>>b>>c;
		a--,b--;
		vec[a].pb(ii(b,c));
		vec[b].pb(ii(a,c));
	}
	sssp(S,0),sssp(T,1),sssp(U,2),sssp(V,3);
	int ans=dist[2][V],mini=INF,m2=INF;
	for (int i = 0; i < n; ++i)
	{
		if((dist[0][i]+dist[1][i])!=dist[0][T])continue;
		if(dist[2][i]<mini)
			mini=dist[2][i],a=i;
		if(dist[3][i]<m2)
			m2=dist[3][i],b=i;
	}
	sssp(a,4),sssp(b,5);
	if((dist[0][a]+dist[1][b]+dist[4][b])==dist[0][T]||(dist[0][b]+dist[1][a]+dist[4][b])==dist[0][T])
		ans=min(ans,mini+m2);
	else{
		int dd=INF;
		for (int i = 0; i < n; ++i)
			if((dist[0][i]+dist[1][a]+dist[4][i])==dist[0][T]||(dist[1][i]+dist[0][a]+dist[4][i])==dist[0][T])
				dd=min(dd,dist[3][i]);
		ans=min(ans,dd+mini);
		dd=INF;
		for (int i = 0; i < n; ++i)
			if((dist[0][i]+dist[1][b]+dist[5][i])==dist[0][T]||(dist[1][i]+dist[0][b]+dist[5][i])==dist[0][T])
				dd=min(dd,dist[2][i]);
		ans=min(ans,dd+m2);
	}
	cout<<ans;
	return 0;
}
//long long
//array bounds
//special cases
//binary search

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 453 ms 21328 KB Output is correct
2 Correct 444 ms 20068 KB Output is correct
3 Correct 443 ms 19944 KB Output is correct
4 Correct 431 ms 20148 KB Output is correct
5 Correct 425 ms 19884 KB Output is correct
6 Correct 456 ms 21428 KB Output is correct
7 Correct 449 ms 20132 KB Output is correct
8 Correct 431 ms 19912 KB Output is correct
9 Correct 474 ms 19956 KB Output is correct
10 Correct 372 ms 19772 KB Output is correct
11 Correct 172 ms 12920 KB Output is correct
12 Correct 495 ms 19984 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 492 ms 20164 KB Output is correct
2 Correct 457 ms 20112 KB Output is correct
3 Correct 453 ms 20124 KB Output is correct
4 Correct 477 ms 20100 KB Output is correct
5 Correct 470 ms 19996 KB Output is correct
6 Correct 442 ms 19780 KB Output is correct
7 Correct 458 ms 19984 KB Output is correct
8 Correct 465 ms 20112 KB Output is correct
9 Correct 462 ms 20100 KB Output is correct
10 Correct 463 ms 20120 KB Output is correct
11 Correct 159 ms 12920 KB Output is correct
12 Correct 454 ms 19764 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2040 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 21 ms 3320 KB Output is correct
5 Correct 13 ms 1912 KB Output is correct
6 Correct 6 ms 504 KB Output is correct
7 Correct 6 ms 504 KB Output is correct
8 Correct 7 ms 632 KB Output is correct
9 Correct 6 ms 508 KB Output is correct
10 Correct 13 ms 1912 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 504 KB Output is correct
15 Correct 5 ms 504 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 453 ms 21328 KB Output is correct
2 Correct 444 ms 20068 KB Output is correct
3 Correct 443 ms 19944 KB Output is correct
4 Correct 431 ms 20148 KB Output is correct
5 Correct 425 ms 19884 KB Output is correct
6 Correct 456 ms 21428 KB Output is correct
7 Correct 449 ms 20132 KB Output is correct
8 Correct 431 ms 19912 KB Output is correct
9 Correct 474 ms 19956 KB Output is correct
10 Correct 372 ms 19772 KB Output is correct
11 Correct 172 ms 12920 KB Output is correct
12 Correct 495 ms 19984 KB Output is correct
13 Correct 492 ms 20164 KB Output is correct
14 Correct 457 ms 20112 KB Output is correct
15 Correct 453 ms 20124 KB Output is correct
16 Correct 477 ms 20100 KB Output is correct
17 Correct 470 ms 19996 KB Output is correct
18 Correct 442 ms 19780 KB Output is correct
19 Correct 458 ms 19984 KB Output is correct
20 Correct 465 ms 20112 KB Output is correct
21 Correct 462 ms 20100 KB Output is correct
22 Correct 463 ms 20120 KB Output is correct
23 Correct 159 ms 12920 KB Output is correct
24 Correct 454 ms 19764 KB Output is correct
25 Correct 14 ms 2040 KB Output is correct
26 Correct 5 ms 504 KB Output is correct
27 Correct 5 ms 376 KB Output is correct
28 Correct 21 ms 3320 KB Output is correct
29 Correct 13 ms 1912 KB Output is correct
30 Correct 6 ms 504 KB Output is correct
31 Correct 6 ms 504 KB Output is correct
32 Correct 7 ms 632 KB Output is correct
33 Correct 6 ms 508 KB Output is correct
34 Correct 13 ms 1912 KB Output is correct
35 Correct 5 ms 376 KB Output is correct
36 Correct 5 ms 376 KB Output is correct
37 Correct 5 ms 376 KB Output is correct
38 Correct 5 ms 504 KB Output is correct
39 Correct 5 ms 504 KB Output is correct
40 Correct 426 ms 20876 KB Output is correct
41 Correct 433 ms 20020 KB Output is correct
42 Correct 443 ms 20044 KB Output is correct
43 Correct 162 ms 12920 KB Output is correct
44 Correct 166 ms 12792 KB Output is correct
45 Correct 380 ms 18824 KB Output is correct
46 Correct 378 ms 19344 KB Output is correct
47 Correct 426 ms 19836 KB Output is correct
48 Correct 178 ms 12792 KB Output is correct
49 Correct 355 ms 20652 KB Output is correct
50 Correct 395 ms 19560 KB Output is correct
51 Correct 365 ms 19360 KB Output is correct