| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 388155 |
2021-04-10T09:40:09 Z |
erfanmir |
Toll (BOI17_toll) |
C++17 |
|
203 ms |
10048 KB |
// In the name of god
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template < class T > using ordered_set = tree < T , null_type , less < T > , rb_tree_tag , tree_order_statistics_node_update >;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define all(x) (x).begin(),(x).end()
#define lc(x) (x) << 1
#define rc(x) (x) << 1 | 1
#define F first
#define S second
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define mp make_pair
ll poww(ll a, ll b, ll md) {
ll ans = 1;
for(; b; b >>= 1, a = a * a % md){
if(b & 1){
ans = ans * a % md;
}
}
return ans % md;
}
const int MAXN = 5e4 + 10;
const int MAXK = 5;
const int SQ = 100;
const int MOD = 1e9 + 7;
const int MOD2 = 998244353;
const ll INF = 1e18;
int n, m, k, q, b;
ll dp[2][MAXN][MAXK], ans[MAXN];
vector<pii> adj[MAXN], que[MAXN];
ll solve(int v, int u){
if(v > u){
return INF;
}
int vk, vq, uk, uq;
ll tmp[MAXK], kmp[MAXK];
for(int i = 0; i < MAXK; i++){
tmp[i] = kmp[i] = INF;
}
vk = v / k;
vq = vk / SQ;
uk = u / k;
uq = uk / SQ;
if(vq == uq){
return dp[b][v][u % k];
}
if(vq < uq){
for(int i = 0; i < k; i++){
tmp[i] = dp[0][v][i];
}
vq++;
}
while(vq < uq){
v = vq * SQ * k;
for(int i = 0; i < k; i++){
kmp[i] = tmp[i];
tmp[i] = INF;
for(int j = 0; j < k; j++){
int x = v + j;
for(auto y : adj[x]){
tmp[i] = min(tmp[i], kmp[y.F % k] + y.S + dp[0][x][i]);
}
}
}
vq++;
}
if(vq == uq){
v = vq * SQ * k;
for(int i = 0; i < k; i++){
kmp[i] = tmp[i];
tmp[i] = INF;
for(int j = 0; j < k; j++){
int x = v + j;
for(auto y : adj[x]){
tmp[i] = min(tmp[i], kmp[y.F % k] + y.S + dp[b][x][i]);
}
}
}
}
return tmp[u % k];
}
int main()
{
scanf("%d %d %d %d", &k, &n, &m, &q);
for(int i = 0; i < m; i++){
int v, u, w;
scanf("%d %d %d", &v, &u, &w);
adj[u].push_back(mp(v, w));
}
for(int i = 0; i < q; i++){
int v, u;
scanf("%d %d", &v, &u);
que[u].push_back(mp(v, i));
}
for(int i = 0; i < 2; i++){
for(int j = 0; j < MAXN; j++){
for(int l = 0; l < MAXK; l++){
dp[i][j][l] = INF;
}
}
}
for(int i = 0; i < n; i++){
int md = i % k;
int sk = i / k;
int sq = sk / SQ;
if(md == 0){
b ^= 1;
}
dp[b][i][md] = 0;
for(int j = sq * SQ * k; j < i - md; j++){
dp[b][j][md] = INF;
for(auto u : adj[i]){
dp[b][j][md] = min(dp[b][j][md], dp[b ^ 1][j][u.F % k] + u.S);
}
}
for(auto u : que[i]){
ans[u.S] = solve(u.F, i);
if(ans[u.S] == INF){
ans[u.S] = -1;
}
}
}
for(int i = 0; i < q; i++){
printf("%lld\n", ans[i]);
}
}
Compilation message
toll.cpp:3: warning: ignoring #pragma comment [-Wunknown-pragmas]
3 | #pragma comment(linker, "/stack:200000000")
|
toll.cpp: In function 'int main()':
toll.cpp:100:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
100 | scanf("%d %d %d %d", &k, &n, &m, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:103:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
103 | scanf("%d %d %d", &v, &u, &w);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:108:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
108 | scanf("%d %d", &v, &u);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
71 ms |
9384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
6476 KB |
Output is correct |
| 3 |
Correct |
4 ms |
6476 KB |
Output is correct |
| 4 |
Correct |
4 ms |
6476 KB |
Output is correct |
| 5 |
Correct |
5 ms |
6604 KB |
Output is correct |
| 6 |
Correct |
5 ms |
6604 KB |
Output is correct |
| 7 |
Correct |
6 ms |
6596 KB |
Output is correct |
| 8 |
Correct |
74 ms |
9340 KB |
Output is correct |
| 9 |
Correct |
73 ms |
9280 KB |
Output is correct |
| 10 |
Correct |
19 ms |
7040 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
203 ms |
10048 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
6476 KB |
Output is correct |
| 2 |
Correct |
4 ms |
6476 KB |
Output is correct |
| 3 |
Correct |
4 ms |
6476 KB |
Output is correct |
| 4 |
Correct |
4 ms |
6476 KB |
Output is correct |
| 5 |
Correct |
4 ms |
6476 KB |
Output is correct |
| 6 |
Correct |
5 ms |
6604 KB |
Output is correct |
| 7 |
Incorrect |
6 ms |
6512 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
6476 KB |
Output is correct |
| 2 |
Correct |
4 ms |
6476 KB |
Output is correct |
| 3 |
Correct |
4 ms |
6476 KB |
Output is correct |
| 4 |
Correct |
4 ms |
6476 KB |
Output is correct |
| 5 |
Correct |
4 ms |
6476 KB |
Output is correct |
| 6 |
Correct |
5 ms |
6604 KB |
Output is correct |
| 7 |
Incorrect |
6 ms |
6512 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
71 ms |
9384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
6476 KB |
Output is correct |
| 3 |
Correct |
4 ms |
6476 KB |
Output is correct |
| 4 |
Correct |
4 ms |
6476 KB |
Output is correct |
| 5 |
Correct |
5 ms |
6604 KB |
Output is correct |
| 6 |
Correct |
5 ms |
6604 KB |
Output is correct |
| 7 |
Correct |
6 ms |
6596 KB |
Output is correct |
| 8 |
Correct |
74 ms |
9340 KB |
Output is correct |
| 9 |
Correct |
73 ms |
9280 KB |
Output is correct |
| 10 |
Correct |
19 ms |
7040 KB |
Output is correct |
| 11 |
Incorrect |
203 ms |
10048 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
