oj.uz

Submission #963678

# Submission time Handle Problem Language Result Execution time Memory
963678 2024-04-15T13:06:21 Z raspy Commuter Pass (JOI18_commuter_pass) C++14
15 / 100
 713 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)
{
	if (u == start)
		return;
	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].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)':
commuter_pass.cpp:25:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   25 |  for (auto [v, i] : pr[u])
      |            ^
commuter_pass.cpp: In function 'int32_t main()':
commuter_pass.cpp:56:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |   auto [d, u] = pq.top();
      |        ^
commuter_pass.cpp:60:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |   for (auto [v, w, i] : graf[u])
      |             ^
commuter_pass.cpp:79:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   79 |   auto [d, u, zs] = pq1.top();
      |        ^
commuter_pass.cpp:89:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   89 |   for (auto [v, w, i] : graf[u])
      |             ^

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 44808 KB Output is correct
2 Runtime error 713 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 271 ms 43056 KB Output is correct
2 Correct 300 ms 45584 KB Output is correct
3 Correct 295 ms 43976 KB Output is correct
4 Correct 270 ms 44992 KB Output is correct
5 Correct 317 ms 46792 KB Output is correct
6 Correct 319 ms 52220 KB Output is correct
7 Correct 294 ms 53952 KB Output is correct
8 Correct 302 ms 45324 KB Output is correct
9 Correct 301 ms 46836 KB Output is correct
10 Correct 250 ms 42656 KB Output is correct
11 Correct 154 ms 42580 KB Output is correct
12 Correct 418 ms 53036 KB Output is correct

Subtask #3
0 / 24.0

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