제출 #444536

#제출 시각아이디문제언어결과실행 시간메모리
444536BeanZToll (BOI17_toll)C++14
7 / 100
414 ms379588 KiB
// I_Love_LPL 1y0m6d #include <bits/stdc++.h> using namespace std; #define ll long long #define endl '\n' const int N = 5e4 + 5; long long mod = 1e9 + 7; const int lim = 4e5 + 5; const int lg = 18; const int base = 37; const long double eps = 1e-6; ll dp[N][lg + 1][5][5], temp[5], res[5]; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); if (fopen("tests.inp", "r")){ freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout); } ll k, n, m, q; cin >> k >> n >> m >> q; for (int i = 0; i < n; i++){ for (int j = 0; j <= lg; j++){ for (int g = 0; g < k; g++){ for (int t = 0; t < k; t++){ dp[i][j][g][t] = 1e18; } } } } for (int i = 1; i <= m; i++){ ll u, v, c; cin >> u >> v >> c; dp[u][0][u % k][v % k] = c; } for (int lo = 1; lo <= lg; lo++){ for (int i = 0; (i + (1 << lo) - 1) < n; i++){ for (int j = 0; j < k; j++){ // des for (int g = 0; g < k; g++){ // trans dp[i][lo][i % k][j] = min(dp[i][lo][i % k][j], dp[i][lo - 1][i % k][g] + dp[i + k * (1 << (lo - 1)) - (i % k) + (g % k)][lo - 1][g % k][j]); } } } } while (q--){ ll u, v; cin >> u >> v; ll dep = (v / k) - (u / k); for (int i = 0; i < k; i++) res[i] = 1e18; res[u % k] = 0; ll cur = u / k; for (int i = 0; i <= lg; i++){ for (int g = 0; g < k; g++) temp[g] = 1e18; if (dep & (1 << i)){ for (int g = 0; g < k; g++){ // des for (int j = 0; j < k; j++){ // trans temp[g] = min(temp[g], res[j] + dp[cur * k + j][i][j][g]); } } cur = cur + (1 << i); for (int g = 0; g < k; g++) res[g] = temp[g]; } } if (res[v % k] < 1e18) cout << res[v % k] << endl; else cout << -1 << endl; } } /* Ans: Out: */

컴파일 시 표준 에러 (stderr) 메시지

toll.cpp: In function 'int main()':
toll.cpp:17:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:18:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...