Submission #511278

#TimeUsernameProblemLanguageResultExecution timeMemory
511278akhan42Toll (BOI17_toll)C++17
100 / 100
359 ms56832 KiB
#include <bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> using namespace std; //using namespace __gnu_pbds; #define F first #define S second #define forn(i, n) for(int i = 0; i < n; ++i) #define forbn(i, b, n) for(int i = b; i < n; ++i) #define sz(v) (int)v.size() #define pb push_back #define eb emplace_back #define all(v) v.begin(), v.end() #define mp make_pair typedef pair<int, int> ii; typedef vector<int> vi; typedef vector<ii> vii; typedef long long ll; //typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; template <class T> inline void mineq(T &a, T b) { a = min(a, b); } template <class T> inline void maxeq(T &a, T b) { a = max(a, b); } const int INF = 1000 * 1000 * 1000; const int MX = 50 * 1000 + 10; const int mxpw = 20; int k, n, m, o; vii gr[MX][mxpw]; void next_pos(vii& positions, vii& npositions, int pw) { vi mns(k, INF); int fac = -1; for(ii pos_t: positions) { int pos = pos_t.F, t = pos_t.S; for(ii nb2_t: gr[pos][pw]) { int nb2 = nb2_t.F, t2 = nb2_t.S; mineq(mns[nb2 % k], t + t2); fac = nb2 / k; } } npositions.clear(); forn(t, k) { if(mns[t] != INF) { npositions.eb(k * fac + t, mns[t]); } } } void solve() { cin >> k >> n >> m >> o; forn(_, m) { int a, b, t; cin >> a >> b >> t; gr[a][0].eb(b, t); } forbn(d, 1, mxpw) forn(a, n) next_pos(gr[a][d - 1], gr[a][d], d - 1); forn(_, o) { int a, b; cin >> a >> b; bool printed = false; int diff = b / k - a / k; if(diff >= 0) { vii positions; positions.eb(a, 0); for(int pw = 0; diff; pw++, diff >>= 1) if(diff & 1) next_pos(positions, positions, pw); for(ii pos: positions) { if(pos.F == b) { cout << pos.S << '\n'; printed = true; } } } if(!printed) cout << -1 << '\n'; } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr); // freopen("262144.in", "r", stdin); // freopen("262144.out", "w", stdout); int t = 1; // cin >> t; while(t--) { solve(); } }
#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...