oj.uz

Submission #963673

# Submission time Handle Problem Language Result Execution time Memory
963673 2024-04-15T12:57:08 Z raspy Commuter Pass (JOI18_commuter_pass) C++14
15 / 100
 755 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)
{
	bool prv = 1;
	for (auto [v, i] : pr[u])
	{
		if (!prv)
			oz++;
		vs[i].insert(oz);
		oznaci(v);
		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);
	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].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)':
commuter_pass.cpp:23:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |  for (auto [v, i] : pr[u])
      |            ^
commuter_pass.cpp: In function 'int32_t main()':
commuter_pass.cpp:54:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |   auto [d, u] = pq.top();
      |        ^
commuter_pass.cpp:58:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |   for (auto [v, w, i] : graf[u])
      |             ^
commuter_pass.cpp:77:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   77 |   auto [d, u, zs] = pq1.top();
      |        ^
commuter_pass.cpp:87:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   87 |   for (auto [v, w, i] : graf[u])
      |             ^

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 45244 KB Output is correct
2 Runtime error 755 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 246 ms 46512 KB Output is correct
2 Correct 295 ms 48880 KB Output is correct
3 Correct 264 ms 47304 KB Output is correct
4 Correct 284 ms 48560 KB Output is correct
5 Correct 342 ms 50168 KB Output is correct
6 Correct 344 ms 55896 KB Output is correct
7 Correct 342 ms 57472 KB Output is correct
8 Correct 311 ms 48860 KB Output is correct
9 Correct 293 ms 50388 KB Output is correct
10 Correct 251 ms 46020 KB Output is correct
11 Correct 154 ms 44672 KB Output is correct
12 Correct 380 ms 56856 KB Output is correct

Subtask #3
0 / 24.0

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