| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 878334 |
2023-11-24T08:21:20 Z |
Danet |
Toll (BOI17_toll) |
C++14 |
|
151 ms |
180720 KB |
/****************************D A N E T****************************
*** ██████╗ █████╗ ███╗ ██╗ ███████╗ ████████╗ ***
*** ██╔══██╗ ██╔══██╗ ████╗ ██║ ██╔════╝ ╚══██╔══╝ ***
*** ██║ ██║ ███████║ ██╔██╗ ██║ █████╗ ██║ ***
*** ██║ ██║ ██╔══██║ ██║╚██╗██║ ██╔══╝ ██║ ***
*** ██████╔╝ ██║ ██║ ██║ ╚████║ ███████╗ ██║ ***
*** ╚═════╝ ╚═╝ ╚═╝ ╚═╝ ╚═══╝ ╚══════╝ ***
****************************D A N E T****************************/
#include <bits/stdc++.h>
using namespace std;
/**************************P R A G M As**************************/
#pragma GCC optimize("O3")
/**************************D E F I N Es**************************/
#define Tof_Io ios_base::sync_with_stdio(false);cin.tie(0) , cout.tie(0);
//#define int long long int
#define double long double
#define pb push_back
#define endl '\n'
#define cond(x) x = x/ l;
/*****************D E F I N Es-F U N C T I O Nes*****************/
#define debug(x) cerr << #x << ": " << x << endl
#define kill(x) cout << x << endl, exit(0)
#define all(x) x.begin(),x.end()
/***************************C O N S Ty***************************/
const double PI = 3.141592653589793;
const int mod = 1e9+7;//1e9+7 998244353
const int inf = 1e9+9;
const int N = 1e5+3;
const int logt = 18;
/***************************B U I L Dy***************************/
int fac[N];
int inv[N];
vector<int> adj[N];
int dp[N][5][5][logt];
int mt[2][5][5];
int n;
int l;
int dx[] = {1,0,-1,0}, dy[] = {0,1,0,-1};
/****************************N O T Ey****************************/
/*
*/
/***********************F U N C T I O N es***********************/
int dnt_pow (int a, int b, int md = mod){int ans = 1; while(b){if(b&1){ans = (a*ans)%md;}a = (a*a)%md;b >>= 1;}return ans ;}
void dnt_bld (){fac[0] = 1; inv[0] = dnt_pow(fac[0],mod-2) ;for(int i = 1 ; i < N ; i++) {fac[i] = (fac[i-1] * i) % mod;inv[i] = dnt_pow( fac[i] , mod-2);}}
int dnt_lis (vector<int> v){if (v.size() == 0) {return 0;} vector<int> vc(v.size(), 0); int len = 1; vc[0] = v[0]; for (int i = 1; i < v.size(); i++) {auto b = vc.begin(), e = vc.begin() + len; auto it = lower_bound(b, e, v[i]); if (it == vc.begin() + len){vc[len++] = v[i];}else{*it = v[i];}} return len;}
int dnt_ncr (int n,int r){return fac[n] * inv[r] % mod * inv[n-r] % mod;}
void dnt_clen (){for (int i = 0; i < 5; i++) mt[0][i][i] = 0;}
/********************************************************************************************************************************/
void slv(int absa)
{
for (int i = 0; i + (1 << absa) - 1 <= n / l + 1; i++)
{
for (int i1 = 0; i1 < l; i1++)
for (int i2 = 0; i2 < l; i2++)
{
for (int i3 = 0; i3 < l; i3++)
{
int cnt = dp[i][i1][i3][absa - 1] + dp[i + (1 << absa - 1)][i3][i2][absa - 1];
dp[i][i1][i2][absa] = min(dp[i][i1][i2][absa], cnt);
}
}
}
}
void solve()
{
int a, b;
cin >> a >> b;
int i1 = a % l;
int i2 = b % l;
cond(a);
cond(b);
memset(mt, 60, sizeof(mt));
dnt_clen();
for (int i = 0; i < 5; i++) mt[0][i][i] = 0;
int cr = 0;
for (int i = logt; i >= 0; i--)
{
if (a + (1 << i) <= b)
{
for (int i1 = 0; i1 < 5; i1++)
for (int i2 = 0; i2 < 5; i2++)
for (int i3 = 0; i3 < 5; i3++)
{
int cnt = mt[cr][i1][i3] + dp[a][i3][i2][i];
if(cnt < mt[cr ^1][i1][i2])
{
mt[cr^1][i1][i2] = cnt;
}
}
memset(mt[cr], 60, sizeof(mt[cr]));
a += (1 << i);
cr = cr ^ 1;
}
}
if (mt[cr][i1][i2] > inf)
{
cout << -1;
return;
}
cout << mt[cr][i1][i2];
}
int32_t main()
{
cin >> l;
int n , m;
cin >> n >> m;
int q;
cin >> q;
memset(dp, 60, sizeof(dp));
for(int i = 0; i < m ; i++)
{
int u, v;
cin >> u >> v;
int w;
cin >> w;
dp[u/l][u%l][v%l][0] = min(dp[u/l][u%l][v%l][0], w);
}
for (int i = 1; (1 << i) <= n / l + 1; i++)
{
slv(i);
}
while (q--)
{
solve();
cout << endl;
}
}
Compilation message
toll.cpp: In function 'int dnt_lis(std::vector<int>)':
toll.cpp:46:135: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | int dnt_lis (vector<int> v){if (v.size() == 0) {return 0;} vector<int> vc(v.size(), 0); int len = 1; vc[0] = v[0]; for (int i = 1; i < v.size(); i++) {auto b = vc.begin(), e = vc.begin() + len; auto it = lower_bound(b, e, v[i]); if (it == vc.begin() + len){vc[len++] = v[i];}else{*it = v[i];}} return len;}
| ~~^~~~~~~~~~
toll.cpp: In function 'void slv(int)':
toll.cpp:59:60: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
59 | int cnt = dp[i][i1][i3][absa - 1] + dp[i + (1 << absa - 1)][i3][i2][absa - 1];
| ~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
132 ms |
180012 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
151 ms |
180720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
179100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
179100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
132 ms |
180012 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
