# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
938796 |
2024-03-05T14:28:50 Z |
vjudge1 |
Toll (BOI17_toll) |
C++17 |
|
3000 ms |
5020 KB |
#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
using namespace std;
const int inf = 1e9;
void dfs(vector<int>& dp, vector<vector<pair<int,int>>>& graph, int cur)
{
for (auto a : graph[cur])
{
dp[a.ff] = min(dp[a.ff],dp[cur]+a.ss);
dfs(dp,graph,a.ff);
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int k,n,m,o;
cin >> k >> n >> m >> o;
if (k==1)
{
vector<int> edges(n-1,inf);
for (int i = 0; i < m; i++)
{
int a,b,c;
cin >> a >> b >> c;
edges[a] = c;
}
vector<int> pref_sum(n-1,0);
pref_sum[0] = edges[0];
for (int i = 1; i < n-1; i++)
pref_sum[i] = pref_sum[i-1]+edges[i];
auto sum = [&](int l,int r)
{
return pref_sum[r] - (l > 0 ? pref_sum[l-1] : 0LL);
};
for (int i = 0; i < o; i++)
{
int a,b;
cin >> a >> b;
if (sum(a,b-1) >= inf)
cout << -1 << '\n';
else
cout << sum(a,b-1) << '\n';
}
}
else
{
//turk milleti meslin baban!!!!
vector<vector<pair<int,int>>> graph(n);
for (int i = 0; i < m; i++)
{
int a,b,t;
cin >> a >> b >> t;
graph[a].push_back({b,t});
}
vector<int> dp(n,inf);
dp[0] = 0;
dfs(dp,graph,0);
for (int i = 0; i < o; i++)
{
int a,b;
cin >> a >> b;
if (dp[b] >= inf)
cout << "-1\n";
else
cout << dp[b] << '\n';
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
1116 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
11 ms |
1272 KB |
Output is correct |
9 |
Correct |
10 ms |
1368 KB |
Output is correct |
10 |
Correct |
3 ms |
1112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3064 ms |
5020 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
1116 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
11 ms |
1272 KB |
Output is correct |
9 |
Correct |
10 ms |
1368 KB |
Output is correct |
10 |
Correct |
3 ms |
1112 KB |
Output is correct |
11 |
Execution timed out |
3064 ms |
5020 KB |
Time limit exceeded |
12 |
Halted |
0 ms |
0 KB |
- |