| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1093560 |
2024-09-27T03:28:40 Z |
Thanhs |
Toll (BOI17_toll) |
C++14 |
|
621 ms |
166272 KB |
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
// #define int long long
#define endl '\n'
#define setmin(x, y) x = ((x) < (y) ? (x) : (y))
#define setmax(x, y) x = ((x) > (y) ? (x) : (y))
mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);}
const int NM = 5e4 + 5;
const int LG = 16;
const int inf = 1e9;
int n, m, q, k;
map<int, int> dp[NM];
struct node
{
int dt[5][5];
node() {for (int i = 0; i < k; i++) for (int j = 0; j < k; j++) dt[i][j] = inf;}
node operator*(const node& o)
{
node res;
for (int i = 0; i < k; i++)
for (int j = 0; j < k; j++)
for (int t = 0; t < k; t++)
setmin(res.dt[i][j], dt[i][t] + o.dt[t][j]);
return res;
}
}st[2][NM][LG];
void solve()
{
cin >> k >> n >> m >> q;
for (int i = 0; i < n; i++)
{
for (int j = (i / k - 1) * k; j < (i / k + 2) * k; j++)
if (j >= 0 && j < n)
dp[i][j] = inf;
dp[i][i] = 0;
}
for (int i = 1; i <= m; i++)
{
int u, v, w;
cin >> u >> v >> w;
setmin(dp[u][v], w);
}
for (int _ = 0; _ <= __lg(n); _++)
for (int i = 0; i < n; i++)
for (int j = (i / k - 1) * k; j < (i / k + 2) * k; j++)
if (j >= 0 && j < n)
{
for (int o = (i / k - 1) * k; o < (i / k + 2) * k; o++)
{
if (o < 0 || o >= n || dp[o].find(j) == dp[o].end())
continue;
setmin(dp[i][j], dp[i][o] + dp[o][j]);
}
}
for (int i = 0; i < n - 1; i++)
{
for (int j = 0; j < k; j++)
st[0][i / k][0].dt[i % k][j] = dp[i][(i / k + 1) * k + j];
for (int j = 0; j < k; j++)
st[1][i / k][0].dt[i % k][j] = dp[i][(i / k - 1) * k + j];
}
for (int lg = 1; lg < __lg(n); lg++)
{
for (int i = 0; i + (1 << lg) - 1 < n / k; i++)
st[0][i][lg] = st[0][i][lg - 1] * st[0][i + (1 << lg - 1)][lg - 1];
for (int i = (1 << lg); i < n / k; i++)
st[1][i][lg] = st[1][i][lg - 1] * st[1][i - (1 << lg - 1)][lg - 1];
}
while (q--)
{
int u, v;
cin >> u >> v;
if (u / k == v / k)
cout << (dp[u][v] == inf ? -1 : dp[u][v]) << endl;
else if (u / k < v / k)
{
node res;
for (int i = 0; i < k; i++)
res.dt[0][i] = dp[u][(u / k + 1) * k + i];
int t = v / k - 1 - u / k, cur = u / k + 1;
for (int i = t ? __lg(t) : -1; i >= 0; i--)
if (t & (1 << i))
{
res = res * st[0][cur][i];
cur += 1 << i;
}
cout << (res.dt[0][v % k] == inf ? -1 : res.dt[0][v % k]) << endl;
}
else
{
node res;
for (int i = 0; i < k; i++)
res.dt[0][i] = dp[u][(u / k - 1) * k + i];
int t = u / k - 1 - v / k, cur = u / k - 1;
for (int i = t ? __lg(t) : -1; i >= 0; i--)
if (t & (1 << i))
{
res = res * st[1][cur][i];
cur -= 1 << i;
}
cout << (res.dt[0][v % k] == inf ? -1 : res.dt[0][v % k]) << endl;
}
}
}
signed main()
{
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
if (fopen("in.txt", "r"))
{
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
}
// freopen("storagebox.inp", "r", stdin);
// freopen("storagebox.out", "w", stdout);
int tc = 1;
// cin >> tc;
while (tc--)
solve();
}
Compilation message
toll.cpp: In function 'void solve()':
toll.cpp:74:66: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
74 | st[0][i][lg] = st[0][i][lg - 1] * st[0][i + (1 << lg - 1)][lg - 1];
| ~~~^~~
toll.cpp:76:66: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
76 | st[1][i][lg] = st[1][i][lg - 1] * st[1][i - (1 << lg - 1)][lg - 1];
| ~~~^~~
toll.cpp: In function 'int main()':
toll.cpp:120:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
120 | freopen("in.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:121:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
121 | freopen("out.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
199 ms |
166272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
621 ms |
95228 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2648 KB |
Output is correct |
| 3 |
Correct |
3 ms |
2652 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2652 KB |
Output is correct |
| 5 |
Correct |
3 ms |
2648 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2652 KB |
Output is correct |
| 7 |
Incorrect |
7 ms |
6112 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2648 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2652 KB |
Output is correct |
| 3 |
Correct |
3 ms |
2788 KB |
Output is correct |
| 4 |
Correct |
3 ms |
2652 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2692 KB |
Output is correct |
| 6 |
Incorrect |
8 ms |
5980 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2648 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2652 KB |
Output is correct |
| 3 |
Correct |
3 ms |
2788 KB |
Output is correct |
| 4 |
Correct |
3 ms |
2652 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2692 KB |
Output is correct |
| 6 |
Incorrect |
8 ms |
5980 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
199 ms |
166272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
