oj.uz

Submission #963680

# Submission time Handle Problem Language Result Execution time Memory
963680 2024-04-15T13:09:02 Z raspy Commuter Pass (JOI18_commuter_pass) C++14
15 / 100
 752 ms 262144 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <unordered_set>
#include <cstring>

#define int long long

using namespace std;

vector<tuple<int, int, int>> graf[100005];
unordered_set<int> vs[200005];
int raz[100005];
int raz1[100005];
vector<pair<int, int>> pr[100005];
int oz = 1;
int start = 0;

void oznaci(int u, int gl)
{
	if (u == start)
		return;
	if (gl > 200005)
		exit(-1);
	bool prv = 1;
	for (auto [v, i] : pr[u])
	{
		if (!prv)
			oz++;
		vs[i].insert(oz);
		oznaci(v, gl+1);
		prv = 0;
	}
}

int32_t main()
{
	int n, m;
	cin >> n >> m;
	int s, t;
	cin >> s >> t;
	start = s;
	int zc, kn;
	cin >> zc >> kn;
	for (int i = 0; i < m; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		graf[u].push_back({v, w, i});
		graf[v].push_back({u, w, i});
	}
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	raz[s] = -1;
	pq.push({0, s});
	while (!pq.empty())
	{
		auto [d, u] = pq.top();
		pq.pop();
		if (d > raz[u] && raz[u] != -1)
			continue;
		for (auto [v, w, i] : graf[u])
		{
			if (raz[v] && raz[v] < d+w)
				continue;
			if (d+w < raz[v])
				pr[v].clear();
			pr[v].push_back({u, i});
			raz[v] = d+w;
			pq.push({raz[v], v});
		}
	}
	oznaci(t, 0);
	priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq1;
	for (int to = 1; to <= oz; to++)
		pq1.push({0, zc, to});
	memset(raz1, -1, sizeof(raz1));
	raz1[zc] = 0;
	while (!pq1.empty())
	{
		auto [d, u, zs] = pq1.top();
		// cout<< u << " " << d << "\n";
		pq1.pop();
		if (d > raz1[u] && raz1[u])
			continue;
		if (u == kn)
		{
			cout << d << "\n";
			exit(0);
		}
		for (auto [v, w, i] : graf[u])
		{
			int ns = d;
			// if (v == 4 && u == 2)
			// 	cout << d << " " << zs << " " << w << " " << (vs[i].find(zs) == vs[i].end()) << "\n";
			if (vs[i].empty() || vs[i].find(zs) == vs[i].end())
				ns+=w;
			if ((raz1[v] != -1 && raz1[v] < ns) || (raz1[v] == d))
				continue;
			// if (u == 3 && v == 2)
				// cout << raz1[v] << " " << ns << " " << d << "\n";
			// cout << "-> " << v << "\n";
			raz1[v] = ns;
			pq1.push({raz1[v], v, zs});
		}
	}
	cout << "error\n";
	exit(0);
	return 0;
}

Compilation message

commuter_pass.cpp: In function 'void oznaci(long long int, long long int)':
commuter_pass.cpp:27:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   27 |  for (auto [v, i] : pr[u])
      |            ^
commuter_pass.cpp: In function 'int32_t main()':
commuter_pass.cpp:58:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |   auto [d, u] = pq.top();
      |        ^
commuter_pass.cpp:62:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   62 |   for (auto [v, w, i] : graf[u])
      |             ^
commuter_pass.cpp:81:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   81 |   auto [d, u, zs] = pq1.top();
      |        ^
commuter_pass.cpp:91:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   91 |   for (auto [v, w, i] : graf[u])
      |             ^

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 43764 KB Output is correct
2 Runtime error 752 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 258 ms 45456 KB Output is correct
2 Correct 313 ms 47876 KB Output is correct
3 Correct 317 ms 46344 KB Output is correct
4 Correct 288 ms 47976 KB Output is correct
5 Correct 326 ms 49416 KB Output is correct
6 Correct 358 ms 55516 KB Output is correct
7 Correct 307 ms 57284 KB Output is correct
8 Correct 345 ms 48312 KB Output is correct
9 Correct 284 ms 49348 KB Output is correct
10 Correct 261 ms 45372 KB Output is correct
11 Correct 158 ms 44880 KB Output is correct
12 Correct 378 ms 56064 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 389 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 306 ms 43764 KB Output is correct
2 Runtime error 752 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -