oj.uz

Submission #924631

# Submission time Handle Problem Language Result Execution time Memory
924631 2024-02-09T10:26:04 Z Baizho Commuter Pass (JOI18_commuter_pass) C++14
100 / 100
 469 ms 51912 KB 
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
  
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
 
 #pragma GCC optimize("Ofast,unroll-loops,fast-math")
 #pragma GCC target("popcnt")
 
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pll;
 
#define sz size()
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define pb push_back
 
const int mod = ll(1e9)+7; //(b + (a%b)) % b (to mod -1%(10^9+7) correctly in c++ its -1 but its suppose to be 10^9+6
const ll MOD = 998244353;  // (a%mod)*(binpow(b,mod-2,mod) = (a/b)%mod
const int N = ll(5e5)+100;
const int M = ll(2e5) + 100;
const long long inf = 5e18;
const long double eps = 1e-15L;
 
ll lcm(ll a, ll b) { return (a / __gcd(a,b))*b; }
 
ll binpow(ll a, ll b, ll m) { ll res=1; a %= m; while(b>0){ if(b&1)res=(res * a) % m; a=(a * a) % m; b/=2; } return res%m;}
 
void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }
 
int n, m, s, t, U, V;
vector<long long> disu(N), disv(N);
vector<pair<long long, long long> > dist(N), diss(N);
vector<pair<int, int> > g[N];

void djik(vector<long long>& dis, int u) {
	for(int i = 1; i <= n; i ++) dis[i] = inf;
	dis[u] = 0;
	set<pair<long long, int> > st;
	st.insert({dis[u], u});
	while(!st.empty()) {
		int v = (*st.begin()).ss;
		st.erase(st.begin());
		for(auto to : g[v]) {
			if(dis[to.ff] > dis[v] + to.ss) {
				if(dis[to.ff] != inf) st.erase({dis[to.ff], to.ff});
				dis[to.ff] = dis[v] + to.ss;;
				st.insert({dis[to.ff], to.ff});
 			}
		}
	}
	
}
  
void Baizho() {
	cin>>n>>m>>s>>t>>U>>V;
	for(int i = 1; i <= m; i ++) {
		int a, b, c; cin>>a>>b>>c;
		g[a].pb({b, c});
		g[b].pb({a, c});
	}
	djik(disu, U); djik(disv, V);
	for(int i = 1; i <= n; i ++) diss[i] = {inf, inf};
	diss[s] = {0, disu[s]};
	set<pair<long long, int> > st;
	st.insert({diss[s].ff, s});
	while(!st.empty()) {
		int v = (*st.begin()).ss;
		st.erase(st.begin());
		for(auto to : g[v]) {
			if(diss[to.ff].ff > diss[v].ff + to.ss) {
				if(diss[to.ff].ff != inf) st.erase({diss[to.ff].ff, to.ff});
				diss[to.ff] = {diss[v].ff + to.ss, min(disu[to.ff], diss[v].ss)};
				st.insert({diss[to.ff].ff, to.ff});
 			} else if(diss[to.ff].ff == diss[v].ff + to.ss) {
 				diss[to.ff].ss = min({diss[to.ff].ss, diss[v].ss, disu[to.ff]});
			 }
		}
	}
	for(int i = 1; i <= n; i ++) dist[i] = {inf, inf};
	dist[t] = {0, disv[t]};
	st.insert({dist[t].ff, t});
	while(!st.empty()) {
		int v = (*st.begin()).ss;
		st.erase(st.begin());
		for(auto to : g[v]) {
			if(dist[to.ff].ff > dist[v].ff + to.ss) {
				if(dist[to.ff].ff != inf) st.erase({dist[to.ff].ff, to.ff});
				dist[to.ff] = {dist[v].ff + to.ss, min(disv[to.ff], dist[v].ss)};
				st.insert({dist[to.ff].ff, to.ff});
 			} else if(dist[to.ff].ff == dist[v].ff + to.ss) {
 				dist[to.ff].ss = min(dist[to.ff].ss, min(disv[to.ff], dist[v].ss));
			 }
		}
	}
	long long ans = disv[U];
//	cout<<diss[t].ff<<endl;
	for(int a = 1; a <= n; a ++) {
//		cout<<diss[a].ff<<" "<<dist[a].ff<<" "<<a<<endl;
		if(diss[a].ff + dist[a].ff == diss[t].ff) {
//			cout<<a<<" "<<diss[a].ss<<" "<<dist[a].ss<<endl;
			ans = min(ans, diss[a].ss + dist[a].ss);
		}
	}
	for(int i = 1; i <= n; i ++) diss[i] = {inf, inf};
	diss[s] = {0, disv[s]};
	st.insert({diss[s].ff, s});
	while(!st.empty()) {
		int v = (*st.begin()).ss;
		st.erase(st.begin());
		for(auto to : g[v]) {
			if(diss[to.ff].ff > diss[v].ff + to.ss) {
				if(diss[to.ff].ff != inf) st.erase({diss[to.ff].ff, to.ff});
				diss[to.ff] = {diss[v].ff + to.ss, min(disv[to.ff], diss[v].ss)};
				st.insert({diss[to.ff].ff, to.ff});
 			} else if(diss[to.ff].ff == diss[v].ff + to.ss) {
 				diss[to.ff].ss = min(diss[to.ff].ss, min(disv[to.ff], diss[v].ss));
			 }
		}
	}
	for(int i = 1; i <= n; i ++) dist[i] = {inf, inf};
	dist[t] = {0, disu[t]};
	st.insert({dist[t].ff, t});
	while(!st.empty()) {
		int v = (*st.begin()).ss;
		st.erase(st.begin());
		for(auto to : g[v]) {
			if(dist[to.ff].ff > dist[v].ff + to.ss) {
				if(dist[to.ff].ff != inf) st.erase({dist[to.ff].ff, to.ff});
				dist[to.ff] = {dist[v].ff + to.ss, min(disu[to.ff], dist[v].ss)};
				st.insert({dist[to.ff].ff, to.ff});
 			} else if(dist[to.ff].ff == dist[v].ff + to.ss) {
 				dist[to.ff].ss = min(dist[to.ff].ss, min(disu[to.ff], dist[v].ss));
			 }
		}
	}
	for(int a = 1; a <= n; a ++) {
//		cout<<diss[a].ff<<" "<<dist[a].ff<<" "<<a<<endl;
		if(diss[a].ff + dist[a].ff == diss[t].ff) {
			ans = min(ans, diss[a].ss + dist[a].ss);
		}
	}
	cout<<ans;
}
 
signed main() {		
// 	Freopen("nondec");
    ios_base::sync_with_stdio(false);   
    cin.tie(0);cout.tie(0); 
//   	precalc();
   	
    int ttt = 1;
//    cin>>ttt;
 
    for(int i=1; i<=ttt; i++) {Baizho(); }
}

Compilation message

commuter_pass.cpp: In function 'void Freopen(std::string)':
commuter_pass.cpp:35:34: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 | void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }
      |                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:35:76: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 | void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }
      |                                                                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 408 ms 44884 KB Output is correct
2 Correct 388 ms 43860 KB Output is correct
3 Correct 371 ms 46160 KB Output is correct
4 Correct 395 ms 47260 KB Output is correct
5 Correct 335 ms 46352 KB Output is correct
6 Correct 440 ms 47188 KB Output is correct
7 Correct 371 ms 46192 KB Output is correct
8 Correct 336 ms 46160 KB Output is correct
9 Correct 355 ms 46340 KB Output is correct
10 Correct 291 ms 46740 KB Output is correct
11 Correct 99 ms 40020 KB Output is correct
12 Correct 383 ms 46164 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 44368 KB Output is correct
2 Correct 442 ms 43856 KB Output is correct
3 Correct 467 ms 45908 KB Output is correct
4 Correct 404 ms 45840 KB Output is correct
5 Correct 427 ms 45840 KB Output is correct
6 Correct 334 ms 45900 KB Output is correct
7 Correct 409 ms 45856 KB Output is correct
8 Correct 410 ms 45844 KB Output is correct
9 Correct 446 ms 45904 KB Output is correct
10 Correct 391 ms 45908 KB Output is correct
11 Correct 105 ms 40100 KB Output is correct
12 Correct 374 ms 45904 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 36188 KB Output is correct
2 Correct 10 ms 35652 KB Output is correct
3 Correct 9 ms 35676 KB Output is correct
4 Correct 18 ms 36888 KB Output is correct
5 Correct 14 ms 36188 KB Output is correct
6 Correct 9 ms 35676 KB Output is correct
7 Correct 10 ms 35584 KB Output is correct
8 Correct 9 ms 35676 KB Output is correct
9 Correct 8 ms 35560 KB Output is correct
10 Correct 13 ms 36188 KB Output is correct
11 Correct 8 ms 35676 KB Output is correct
12 Correct 8 ms 35676 KB Output is correct
13 Correct 8 ms 35676 KB Output is correct
14 Correct 9 ms 35676 KB Output is correct
15 Correct 9 ms 35676 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 408 ms 44884 KB Output is correct
2 Correct 388 ms 43860 KB Output is correct
3 Correct 371 ms 46160 KB Output is correct
4 Correct 395 ms 47260 KB Output is correct
5 Correct 335 ms 46352 KB Output is correct
6 Correct 440 ms 47188 KB Output is correct
7 Correct 371 ms 46192 KB Output is correct
8 Correct 336 ms 46160 KB Output is correct
9 Correct 355 ms 46340 KB Output is correct
10 Correct 291 ms 46740 KB Output is correct
11 Correct 99 ms 40020 KB Output is correct
12 Correct 383 ms 46164 KB Output is correct
13 Correct 417 ms 44368 KB Output is correct
14 Correct 442 ms 43856 KB Output is correct
15 Correct 467 ms 45908 KB Output is correct
16 Correct 404 ms 45840 KB Output is correct
17 Correct 427 ms 45840 KB Output is correct
18 Correct 334 ms 45900 KB Output is correct
19 Correct 409 ms 45856 KB Output is correct
20 Correct 410 ms 45844 KB Output is correct
21 Correct 446 ms 45904 KB Output is correct
22 Correct 391 ms 45908 KB Output is correct
23 Correct 105 ms 40100 KB Output is correct
24 Correct 374 ms 45904 KB Output is correct
25 Correct 13 ms 36188 KB Output is correct
26 Correct 10 ms 35652 KB Output is correct
27 Correct 9 ms 35676 KB Output is correct
28 Correct 18 ms 36888 KB Output is correct
29 Correct 14 ms 36188 KB Output is correct
30 Correct 9 ms 35676 KB Output is correct
31 Correct 10 ms 35584 KB Output is correct
32 Correct 9 ms 35676 KB Output is correct
33 Correct 8 ms 35560 KB Output is correct
34 Correct 13 ms 36188 KB Output is correct
35 Correct 8 ms 35676 KB Output is correct
36 Correct 8 ms 35676 KB Output is correct
37 Correct 8 ms 35676 KB Output is correct
38 Correct 9 ms 35676 KB Output is correct
39 Correct 9 ms 35676 KB Output is correct
40 Correct 458 ms 51912 KB Output is correct
41 Correct 380 ms 48468 KB Output is correct
42 Correct 435 ms 48464 KB Output is correct
43 Correct 89 ms 40684 KB Output is correct
44 Correct 82 ms 40912 KB Output is correct
45 Correct 271 ms 47280 KB Output is correct
46 Correct 241 ms 46932 KB Output is correct
47 Correct 469 ms 48748 KB Output is correct
48 Correct 88 ms 40284 KB Output is correct
49 Correct 331 ms 51348 KB Output is correct
50 Correct 288 ms 47208 KB Output is correct
51 Correct 242 ms 47204 KB Output is correct