oj.uz

Submission #714683

# Submission time Handle Problem Language Result Execution time Memory
714683 2023-03-25T07:52:03 Z Iliya Toll (BOI17_toll) C++17
0 / 100
 37 ms 3620 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];
vector<pair<int, int>> Order;
int k, n, m, o;
void Subtask1() 
{
	vector<int> dp(n);
	for (int i = 0; i < n; i++) 
		for (auto [u, w] : Adj[i]) 
			dp[u] = dp[i] + w;
	for (auto [l, r] : Order)
		printf("%d\n", dp[r] - dp[l]);
}
void Subtask2()
{
	vector<int> dp(n, Inf);
	dp[0] = 0;
	for (int i = 0; i < n; i++) 
	{
		if (dp[i] == Inf) continue;
		for (auto [u, w] : Adj[i]) 
			dp[u] = min(dp[u], dp[i] + w);
	}
	for (auto [l, r] : Order) 
		printf("%d\n", (dp[r] == Inf ? -1 : dp[r]));
}
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);
	}
	int cnt = 0;
	for (int i = 0; i < o; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		Order.emplace_back(a, b);
		if (a == 0) cnt++;
	}
	if (k == 1) {Subtask1(); return 0;}
	if (cnt == o) {Subtask2(); return 0;} 
	printf("-1");
	return 0;
}

Compilation message

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

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3620 KB Output is correct
2 Incorrect 1 ms 1476 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 3608 KB Output is correct
2 Incorrect 1 ms 1364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3620 KB Output is correct
2 Incorrect 1 ms 1476 KB Output isn't correct
3 Halted 0 ms 0 KB -