# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
838941 |
2023-08-28T10:08:44 Z |
danitro |
Toll (BOI17_toll) |
C++14 |
|
3000 ms |
217536 KB |
#include <bits/stdc++.h>
using namespace std;
#define MAX 51000
int k, n, m, q, a, b, c, dist[5][MAX], ans[MAX];
struct Query
{
int u, v, l, r, idx;
};
vector<Query> t;
vector<pair<int, int> > gr[MAX];
void find_dist(int ost, int l, int r, int p)
{
dist[ost][k * l + ost] = 0;
queue<int> q;
q.push(k * l + ost);
int node;
while(!q.empty())
{
node = q.front();
q.pop();
if(node / k == r)continue;
for(int i = 0; i < gr[node].size(); i++)
{
//if(gr[node][i].first / k > max(l, r) + 1 || gr[node][i].first / k < min(l, r) - 1)continue;
if(node / k == gr[node][i].first / k + p)
{
q.push(gr[node][i].first);
dist[ost][gr[node][i].first] = min(dist[ost][gr[node][i].first],
dist[ost][node] + gr[node][i].second);
}
}
}
return;
}
void solve(int l, int r, vector<Query>& t)
{
if(l >= r || t.size() == 0)return;
int mid = (l + r) / 2;
for(int i = 0; i < 5; i++)fill(dist[i] + l * k, dist[i] + r * k + k, INT_MAX / 3);
for(int i = 0; i < k; i++)find_dist(i, mid, r, 1);
for(int i = 0; i < k; i++)find_dist(i, mid, l, -1);
vector<Query> todo[2];
for(auto q : t)
{
if(q.l <= mid && mid <= q.r)
{
for(int j = 0; j < k; j++)
{
ans[q.idx] = min(ans[q.idx], dist[j][q.u] + dist[j][q.v]);
}
}
else todo[q.l > mid].push_back(q);
}
solve(l, mid - 1, todo[0]);
solve(mid + 1, r, todo[1]);
return ;
}
int main()
{
scanf("%d%d%d%d", &k, &n, &m, &q);
for(int i = 0; i < m; i++)
{
scanf("%d%d%d", &a, &b, &c);
gr[a].push_back({b, c});
gr[b].push_back({a, c});
}
t.resize(q);
for(int i = 0; i < q; i++)
{
scanf("%d%d", &t[i].u, &t[i].v);
t[i].l = t[i].u / k;
t[i].r = t[i].v / k;
t[i].idx = i;
}
fill(ans, ans + q, INT_MAX / 2);
solve(0, n / k, t);
for(int i = 0; i < q; i++)
{
if(ans[i] > INT_MAX / 5)printf("-1\n");
else printf("%d\n", ans[i]);
}
return 0;
}
/*
5 14 5 5
0 5 9
5 12 10
0 7 7
7 12 8
4 7 10
0 12
0 5
0 7
7 12
0 13
1 8 7 1
0 1 10
1 2 1
2 3 6
3 4 4
4 5 4
5 6 3
6 7 2
2 3
*/
Compilation message
toll.cpp: In function 'void find_dist(int, int, int, int)':
toll.cpp:30:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for(int i = 0; i < gr[node].size(); i++)
| ~~^~~~~~~~~~~~~~~~~
toll.cpp: In function 'int main()':
toll.cpp:75:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
75 | scanf("%d%d%d%d", &k, &n, &m, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
79 | scanf("%d%d%d", &a, &b, &c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
87 | scanf("%d%d", &t[i].u, &t[i].v);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
438 ms |
4512 KB |
Output is correct |
2 |
Incorrect |
1 ms |
1492 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3071 ms |
217536 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
1492 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
1492 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
438 ms |
4512 KB |
Output is correct |
2 |
Incorrect |
1 ms |
1492 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |