oj.uz

Submission #963797

# Submission time Handle Problem Language Result Execution time Memory
963797 2024-04-15T17:03:43 Z raspy Commuter Pass (JOI18_commuter_pass) C++14
15 / 100
 2000 ms 29528 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <unordered_set>
#include <cstring>

#define inf 1'000'000'000'000
#define int long long

using namespace std;
typedef pair<int, int> ii;

vector<pair<int, int>> graf[100005];
vector<int> par[100005];
pair<int, int> dp[100005];

void dij(int st, vector<int>& dist, bool dg = false)
{
	priority_queue<ii, vector<ii>, greater<ii>> pq;
	pq.push({0, st});
	dist[st] = 0;
	while (!pq.empty())
	{
		auto [d, u] = pq.top();
		pq.pop();
		if (d > dist[u])
			continue;
		for (auto [v, w] : graf[u])
		{
			if (dist[v] != -1 && d+w > dist[v])
				continue;
			if (dg)
			{
				if (d+w == dist[v])
				{
					par[v].push_back(u);
					continue;
				}
				par[v].clear();
				par[v].push_back(u);
				// cout << u << "->" << v << "\n";
			}
			else if (d+w == dist[v])
				continue;
			dist[v] = d+w;
			pq.push({dist[v], v});
		}
	}
}

int gl = 0;
pair<int, int> dfs(vector<int>& dist1, vector<int>& dist2, int vz)
{
	if (dp[vz].first != 0)
		return dp[vz];
	pair<int, int> rez = {dist1[vz], dist2[vz]};
	for (int v : par[vz])
	{
		gl++;
		auto[nu, nv] = dfs(dist1, dist2, v);
		gl--;
		if (nu < rez.first)
		{
			rez.first = nu;
			rez.second = min(dist2[vz], nv);
		}
		else if (nv < rez.second)
		{
			rez.second = nv;
			rez.first = min(dist1[vz], nu);
		}
	}
	return dp[vz] = rez;
}

int32_t main()
{
	int n, m;
	cin >> n >> m;
	int s, t;
	cin >> s >> t;
	int u, v;
	cin >> u >> v;
	for (int i = 0; i < m; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		graf[u].push_back({v, w});
		graf[v].push_back({u, w});
	}
	vector<int> dist2(n+1, -1);
	vector<int> dist3(n+1, -1);
	dij(s, dist2, true);
	fill(dist2.begin(), dist2.end(), -1);
	dij(u, dist2);
	dij(v, dist3);
	int rez = dist2[v];
	pair<int, int> par = dfs(dist2, dist3, t);
	cout << min(rez, par.first+par.second) << "\n";
	// for (int i = 1; i <= n; i++)
	// 	cout << dp[i].first << " " << dp[i].second << "\n";
	return 0;
}

Compilation message

commuter_pass.cpp: In function 'void dij(long long int, std::vector<long long int>&, bool)':
commuter_pass.cpp:25:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   25 |   auto [d, u] = pq.top();
      |        ^
commuter_pass.cpp:29:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |   for (auto [v, w] : graf[u])
      |             ^
commuter_pass.cpp: In function 'std::pair<long long int, long long int> dfs(std::vector<long long int>&, std::vector<long long int>&, long long int)':
commuter_pass.cpp:61:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |   auto[nu, nv] = dfs(dist1, dist2, v);
      |       ^

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 27860 KB Output is correct
2 Execution timed out 2069 ms 26148 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 25844 KB Output is correct
2 Correct 316 ms 26276 KB Output is correct
3 Correct 308 ms 25488 KB Output is correct
4 Correct 370 ms 26000 KB Output is correct
5 Correct 335 ms 26512 KB Output is correct
6 Correct 309 ms 28716 KB Output is correct
7 Correct 364 ms 29528 KB Output is correct
8 Correct 327 ms 25984 KB Output is correct
9 Correct 300 ms 26512 KB Output is correct
10 Correct 296 ms 25800 KB Output is correct
11 Correct 157 ms 23292 KB Output is correct
12 Correct 362 ms 29156 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 8284 KB Output is correct
2 Correct 3 ms 6492 KB Output is correct
3 Incorrect 2 ms 6492 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 27860 KB Output is correct
2 Execution timed out 2069 ms 26148 KB Time limit exceeded
3 Halted 0 ms 0 KB -