Submission #480713

#TimeUsernameProblemLanguageResultExecution timeMemory
480713hidden1Toll (BOI17_toll)C++14
46 / 100
3066 ms16100 KiB
#include <bits/stdc++.h> using namespace std; //#pragma GCC optimize ("O3") //#pragma GCC target ("sse4") #define endl "\n" typedef long long ll; template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;} template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;} template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; } template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; } const ll mod = 1e15 + 7; #ifndef LOCAL #define cerr if(false) cerr #endif typedef vector<vector<ll> > mat; const ll MAX_N = 1e5 + 10; ll n, m, k, q; mat mult(const mat &a, const mat &b) { mat ret = mat(k, vector<ll>(k, mod)); if(a.empty()) { return b; } if(b.empty()) { return a; } for(ll i = 0; i < k; i ++) { for(ll j = 0; j < k; j ++) { for(ll mid = 0; mid < k; mid ++) { chkmin(ret[i][j], a[i][mid] + b[mid][j]); } } } return ret; } mat prec[MAX_N], jmp[MAX_N]; const ll JMP = 750; ll loc[MAX_N]; vector<pair<ll, ll> > g[MAX_N]; signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> k >> n >> m >> q; for(ll i = 0; i < m; i ++) { ll a, b, c; cin >> a >> b >> c; g[a].push_back({b, c}); } for(ll i = 0; i < n; i += k) { prec[i / k] = mat(k, vector<ll>(k, mod)); for(ll j = i; j < i + k; j ++) { for(auto it : g[j]) { chkmin(prec[i / k][j % k][it.first % k], it.second); } } } fill(loc, loc + MAX_N, mod); for(ll i = (n + k - 1) / k; i >= 0; i --) { if(i % JMP == 0) { jmp[i / k] = prec[i / k]; loc[i / k] = i / k + 1; } else { jmp[i / k] = mult(prec[i / k], jmp[i / k + 1]); loc[i / k] = loc[i / k + 1]; } } while(q --) { ll a, b; cin >> a >> b; if(a / k >= b / k) { cout << -1 << endl; continue; } mat ret = prec[a / k]; a += k; ll gra = a / k, grb = b / k; while(gra < grb) { if(loc[gra] < grb) { ret = mult(ret, jmp[gra]); gra = loc[gra]; } else { ret = mult(ret, prec[gra]); gra ++; } } if(ret[a % k][b % k] == mod) { cout << -1 << endl; } else { cout << ret[a % k][b % k] << endl; } } return 0; }
#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...