제출 #916319

#제출 시각아이디문제언어결과실행 시간메모리
916319trMatherzToll (BOI17_toll)C++17
7 / 100
747 ms326736 KiB
#include <iostream> //cin, cout /* #include <fstream> std::ifstream cin ("ex.in"); std::ofstream cout ("ex.out"); */ // includes #include <cmath> #include <set> #include <map> #include <queue> #include <string> #include <vector> #include <array> #include <algorithm> #include <numeric> #include <iomanip> #include <unordered_set> #include <stack> #include <ext/pb_ds/assoc_container.hpp> #include <random> #include <chrono> //usings using namespace std; using namespace __gnu_pbds; // misc #define ll long long #define pb push_back #define pq priority_queue #define ub upper_bound #define lb lower_bound template<typename T, typename U> bool emin(T &a, const U &b){ return b < a ? a = b, true : false; } template<typename T, typename U> bool emax(T &a, const U &b){ return b > a ? a = b, true : false; } typedef uint64_t hash_t; // vectors #define vi vector<int> #define vvi vector<vi> #define vvvi vector<vvi> #define vpii vector<pair<int, int>> #define vvpii vector<vector<pair<int, int>>> #define vppipi vector<pair<int, pair<int, int>>> #define vl vector<ll> #define vvl vector<vl> #define vvvl vector<vvl> #define vpll vector<pair<ll, ll>> #define vb vector<bool> #define vvb vector<vb> #define vs vector<string> #define sz(x) (int)x.size() #define rz resize #define all(x) x.begin(), x.end() // pairs #define pii pair<int, int> #define pll pair<ll, ll> #define mp make_pair #define f first #define s second // sets #define si set<int> #define sl set<ll> #define ss set<string> #define in insert template <class T> using iset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; // maps #define mii map<int, int> #define mll map<ll, ll> // loops #define FR(x, z, y) for (int x = z; x < y; x++) #define FRE(x, z, y) FR(x, z, y + 1) #define F(x, y) FR(x, 0, y) #define FE(x, y) F(x, y + 1) #define A(x, y) for(auto &x : y) vvl dp[50'005][17]; int main(){ F(i, 50'005) F(j, 17) dp[i][j] = vvl(5, vl(5, 1e12)); int k, n, m, q; cin >> k >> n >> m >> q; while(m--){ int x, y, z; cin >> x >> y >> z; dp[x / k][0][x % k][y % k] = z; } FR(j, 1, 17) for(int i = 0; i + (1 << j) < (n + k - 1); i++) F(l, 5) F(p, 5) F(u, 5) emin(dp[i][j][l][p], dp[i][j - 1][l][u] + dp[i + (1 << j - 1)][j - 1][u][p]); while(q--){ int x, y; cin >> x >> y; vvl ans = vvl(5, vl(5, 0)); int cur = x; for(int i = 16; i >= 0; i--){ if(((y / k) - (x / k)) & (1 << i)){ vvl temp = vvl(5, vl(5, 1e12)); F(l, 5) F(p, 5) F(u, 5) emin(temp[l][p], ans[l][u] + dp[cur / k][i][u][p]); cur += (1 << i); ans = temp; } } cout << (ans[x % k][y % k] == 1e12 ? -1 : ans[x % k][y % k]) << endl; } return 0; }

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

toll.cpp: In function 'int main()':
toll.cpp:100:66: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  100 |         emin(dp[i][j][l][p], dp[i][j - 1][l][u] + dp[i + (1 << j - 1)][j - 1][u][p]);
      |                                                                ~~^~~
#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...