oj.uz

Submission #963795

# Submission time Handle Problem Language Result Execution time Memory
963795 2024-04-15T16:57:30 Z raspy Commuter Pass (JOI18_commuter_pass) C++14
15 / 100
 1107 ms 262144 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].clear();
				// cout << u << "->" << v << "\n";
				par[v].push_back(u);
			}
			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> dist1(n+1, -1);
	vector<int> dist2(n+1, -1);
	vector<int> dist3(n+1, -1);
	dij(s, dist1, true);
	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:55:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |   auto[nu, nv] = dfs(dist1, dist2, v);
      |       ^

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 29248 KB Output is correct
2 Runtime error 1107 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 28024 KB Output is correct
2 Correct 339 ms 28440 KB Output is correct
3 Correct 317 ms 27852 KB Output is correct
4 Correct 369 ms 28172 KB Output is correct
5 Correct 347 ms 28868 KB Output is correct
6 Correct 335 ms 31220 KB Output is correct
7 Correct 338 ms 31656 KB Output is correct
8 Correct 314 ms 28304 KB Output is correct
9 Correct 319 ms 28760 KB Output is correct
10 Correct 374 ms 27844 KB Output is correct
11 Correct 166 ms 24832 KB Output is correct
12 Correct 326 ms 31580 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 430 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 29248 KB Output is correct
2 Runtime error 1107 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -