oj.uz

Submission #960362

# Submission time Handle Problem Language Result Execution time Memory
960362 2024-04-10T10:08:23 Z MrNanama Commuter Pass (JOI18_commuter_pass) C++17
15 / 100
 2000 ms 84172 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back

using namespace std;
using ll = long long;

ll n,m,s,t,u,v;
ll ans;
vector<vector<pair<ll,ll>>> neigh;
unordered_map<ll, unordered_map<ll,ll>> dist;

vector<vector<ll>> parents;
vector<vector<ll>> kids;
vector<bool> important;

vector<ll> ds;
vector<ll> du;
vector<ll> dv;
vector<ll> dt;

vector<ll> dp_u;
vector<ll> dp_v;

void djkstra1(ll st, ll en){
	vector<bool> visited;
	vector<vector<int>> came_from;

	visited.assign(n,0);
	came_from.resize(n);
	important.assign(n,0);

	priority_queue<array<ll,3>, vector<array<ll,3>>, greater<array<ll,3>>> tasks;
	//tasks.push({0,st,st});

	ds[st] = 0;
	for(pair<ll,ll> go:neigh[st]){
		tasks.push({go.se, go.fi, st});
	}	


	while(!tasks.empty()){
		ll c = (tasks.top())[0];
		ll tar = (tasks.top())[1];
		ll fro = (tasks.top())[2];
		tasks.pop();


		if(ds[tar] == LLONG_MAX){
			ds[tar] = c;
			came_from[tar].pb(fro);
			parents[tar].pb(fro);
			kids[fro].pb(tar);
		}else if(c == ds[tar]){
			came_from[tar].pb(fro);
			parents[tar].pb(fro);
			kids[fro].pb(tar);
		}

		if(visited[tar]){continue;}

		for(pair<ll,ll> go:neigh[tar]){
			tasks.push({c+go.se, go.fi, tar});
		}

		visited[tar] = 1;
	}


	important[en] = 1;
	queue<ll> valuables;
	valuables.push(en);

	while(!valuables.empty()){
		ll curr = valuables.front();
		valuables.pop();

		for(ll a:parents[curr]){
			if(important[a] == 0){
				//this is unnecessary
				if(ds[a]+dist[a][curr] == ds[curr]){
					important[a] = 1; valuables.push(a);
				}
			}
		}
	}


	/*
	for(ll i=0; i<n; i++){
		cout << "imp " << i+1 << " " << important[i] << endl;
	}
	*/

	for(ll i=0; i<n; i++){
		if(important[i] == 0){
			parents[i].clear();
			kids[i].clear();
		}

		vector<ll> psd;
		for(int a:parents[i]){
			if(important[a]){psd.pb(a);}
		}

		parents[i] = psd;

		psd.clear();
		for(int a:kids[i]){
			if(important[a]){psd.pb(a);}
		}

		kids[i] = psd;
	}

	/*
	for(ll i=0; i<n; i++){
		cout << i+1 << ": ";
		for(ll go:kids[i]){
			cout << go+1 << " ";
		}
		cout << endl;
	}
	*/

}

void djkstra2(vector<ll> &vec, ll st){

	priority_queue<array<ll,3>, vector<array<ll,3>>, greater<array<ll,3>>> tasks;

	vector<ll> visited;
	visited.assign(n,0);

	vec[st] = 0;
	visited[st] = 1;

	for(pair<ll,ll> a:neigh[st]){
		tasks.push({a.se, a.fi, st});
	}

	while(!tasks.empty()){
		ll c = tasks.top()[0];
		ll tar = tasks.top()[1];
		ll fro = tasks.top()[2];

		tasks.pop();

		if(visited[tar]){continue;}
		visited[tar] = 1;
		vec[tar] = c;

		for(pair<ll,ll> go:neigh[tar]){
			tasks.push({c+go.se, go.fi});
		}
	}

}

inline void calc_dp_u(ll node){
	dp_u[node] = min<ll>(du[node],dp_u[node]);

	for(ll p:parents[node]){
		dp_u[node] = min<ll>(dp_u[p], dp_u[node]);
	}

	for(ll go:kids[node]){
		calc_dp_u(go);
	}
}

inline void calc_dp_v(ll node){
	dp_v[node] = min<ll>(dv[node],dp_v[node]);

	for(ll p:kids[node]){
		dp_v[node] = min<ll>(dp_v[p], dp_v[node]);
	}

	for(ll go:parents[node]){
		calc_dp_v(go);
	}
}

void dfs(ll node, ll &psd_ans){
	//maybe a protection against llong_max sum
	psd_ans = min<ll>(dp_u[node]+dp_v[node], psd_ans);

	for(ll go:kids[node]){dfs(go, psd_ans);}
}

ll solve(){
	ds.clear();
	ds.assign(n, LLONG_MAX);
	dt.clear();
	dt.assign(n, LLONG_MAX);
	du.clear();
	du.assign(n, LLONG_MAX);
	dv.clear();
	dv.assign(n, LLONG_MAX);

	dp_u.clear();
	dp_u.assign(n, LLONG_MAX);
	dp_v.clear();
	dp_v.assign(n, LLONG_MAX);

	parents.clear();
	parents.resize(n);
	kids.clear();
	kids.resize(n);
	important.clear();
	important.assign(n,0);

	djkstra1(s,t);
	djkstra2(du, u);
	djkstra2(dv, v);
	djkstra2(dt, t);

	calc_dp_u(s);
	calc_dp_v(t);

	ll psd_ans = LLONG_MAX;

	dfs(s, psd_ans);

	return psd_ans;

	return 0;
}


int main(){

	ios_base::sync_with_stdio(false); cin.tie(NULL);
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);

	cin >> n >> m >> s >> t >> u >> v;
	s--; t--; u--; v--;
	neigh.resize(n);
	parents.resize(n);
	kids.resize(n);

	ds.assign(n, LLONG_MAX);


	for(ll i=0; i<m; i++){
		ll n1,n2,c;
		cin >> n1 >> n2 >> c;
		n1--; n2--;

		neigh[n1].pb({n2,c});
		neigh[n2].pb({n1,c});

		dist[n1][n2] = c;
		dist[n2][n1] = c;
	}

	ans = solve();

	/*
	for(ll i=0; i<n; i++){
		cout << i+1 << ": ";
		for(int a:kids[i]){
			cout << a+1 << " ";
		}
		cout << endl;
	}
	*/

	ll psd;

	/*
	psd = s;
	s = t;
	t = psd;
	*/

	psd = u;
	u = v;
	v = psd;

	ans = min<ll>(ans, solve());
	ans = min<ll>(ans, du[v]);

	cout << ans << endl;
}

Compilation message

commuter_pass.cpp: In function 'void djkstra2(std::vector<long long int>&, ll)':
commuter_pass.cpp:146:6: warning: unused variable 'fro' [-Wunused-variable]
  146 |   ll fro = tasks.top()[2];
      |      ^~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1132 ms 78468 KB Output is correct
2 Execution timed out 2051 ms 77984 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1114 ms 78680 KB Output is correct
2 Correct 1014 ms 80948 KB Output is correct
3 Correct 1031 ms 79568 KB Output is correct
4 Correct 1065 ms 74816 KB Output is correct
5 Correct 1016 ms 76492 KB Output is correct
6 Correct 1089 ms 82980 KB Output is correct
7 Correct 1088 ms 84172 KB Output is correct
8 Correct 1031 ms 75964 KB Output is correct
9 Correct 1080 ms 83084 KB Output is correct
10 Correct 1048 ms 79228 KB Output is correct
11 Correct 452 ms 58916 KB Output is correct
12 Correct 1072 ms 81768 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2033 ms 5776 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1132 ms 78468 KB Output is correct
2 Execution timed out 2051 ms 77984 KB Time limit exceeded
3 Halted 0 ms 0 KB -