oj.uz

Submission #714717

# Submission time Handle Problem Language Result Execution time Memory
714717 2023-03-25T08:22:15 Z Iliya Toll (BOI17_toll) C++17
18 / 100
 3000 ms 6040 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e4 + 10;
const int Inf = 0x3f3f3f3f;
vector<pair<int, int>> Adj[N], Order[N];
int n, m, k, o, D[N], mark[N], ans[N];
void Dijkstra(int v) 
{
	memset(D, 63, sizeof D);
	memset(mark, 0, sizeof mark);
	D[v] = 0;
	priority_queue<pair<int, int>> PQ;
	PQ.emplace(0, v);
	while (!PQ.empty()) 
	{
		int v = PQ.top().second; PQ.pop();
		if (mark[v]) continue;
		mark[v] = true;
		for (auto [u, w] : Adj[v]) 
			if (D[u] > D[v] + w)
				D[u] = D[v] + w, PQ.emplace(-D[u], u);
	}
}
signed main() 
{	
	scanf("%d%d%d%d", &k, &n, &m, &o);
	for (int i = 0; i < m; i++) 
	{
		int a, b, t;
		scanf("%d%d%d", &a, &b, &t);
		Adj[a].emplace_back(b, t);
	}
	vector<int> V;
	for (int i = 0; i < o; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		Order[a].emplace_back(b, i);
		V.push_back(a);
	}
	sort(V.begin(), V.end());
	V.resize(unique(V.begin(), V.end()) - V.begin());
	for (int x : V) 
	{
		Dijkstra(x);
		for (auto [u, i] : Order[x])
			ans[i] = D[u];
	}
	for (int i = 0; i < o; i++) 
		printf("%d\n", (ans[i] == Inf ? -1 : ans[i]));
	return 0;
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |  scanf("%d%d%d%d", &k, &n, &m, &o);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:31:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |   scanf("%d%d%d", &a, &b, &t);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3083 ms 4940 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 4808 KB Output is correct
2 Correct 2 ms 3028 KB Output is correct
3 Correct 2 ms 3048 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 2 ms 3028 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 4 ms 3360 KB Output is correct
8 Correct 5 ms 3436 KB Output is correct
9 Correct 23 ms 5040 KB Output is correct
10 Correct 60 ms 6040 KB Output is correct
11 Correct 44 ms 5192 KB Output is correct
12 Correct 30 ms 4864 KB Output is correct
13 Correct 56 ms 6012 KB Output is correct
14 Correct 34 ms 4852 KB Output is correct
15 Correct 29 ms 4572 KB Output is correct
16 Correct 30 ms 4536 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 2 ms 3028 KB Output is correct
3 Correct 2 ms 3028 KB Output is correct
4 Correct 2 ms 3040 KB Output is correct
5 Correct 2 ms 3044 KB Output is correct
6 Correct 3 ms 3028 KB Output is correct
7 Correct 6 ms 3028 KB Output is correct
8 Correct 11 ms 3180 KB Output is correct
9 Correct 9 ms 3028 KB Output is correct
10 Correct 24 ms 4772 KB Output is correct
11 Correct 231 ms 4776 KB Output is correct
12 Correct 337 ms 5580 KB Output is correct
13 Correct 372 ms 6028 KB Output is correct
14 Correct 312 ms 5360 KB Output is correct
15 Correct 203 ms 4460 KB Output is correct
16 Correct 201 ms 4528 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 2 ms 3028 KB Output is correct
3 Correct 2 ms 3028 KB Output is correct
4 Correct 2 ms 3040 KB Output is correct
5 Correct 2 ms 3044 KB Output is correct
6 Correct 3 ms 3028 KB Output is correct
7 Correct 6 ms 3028 KB Output is correct
8 Correct 11 ms 3180 KB Output is correct
9 Correct 9 ms 3028 KB Output is correct
10 Correct 24 ms 4772 KB Output is correct
11 Correct 231 ms 4776 KB Output is correct
12 Correct 337 ms 5580 KB Output is correct
13 Correct 372 ms 6028 KB Output is correct
14 Correct 312 ms 5360 KB Output is correct
15 Correct 203 ms 4460 KB Output is correct
16 Correct 201 ms 4528 KB Output is correct
17 Execution timed out 3080 ms 4900 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3083 ms 4940 KB Time limit exceeded
2 Halted 0 ms 0 KB -