제출 #1093549

#제출 시각아이디문제언어결과실행 시간메모리
1093549coldbr3wToll (BOI17_toll)C++17
0 / 100
238 ms328788 KiB
#include <bits/stdc++.h> using namespace std; #define ll int #define pll pair<long long, long long> #define pb push_back #define F first #define S second #define all(x) (x).begin(), (x).end() const ll N = 2e5 + 100; const ll inf = 1e9; const ll mod = 1e9 + 7; const ll block = 450; ll k,n,m,q; struct Matrix{ vector<vector<ll>>d; ll n,m; void init(ll _n, ll _m){ n = _n; m = _m; d.resize(n, vector<ll>(m)); } ll col() const{ return m; } ll row() const{ return n; } }; Matrix operator* (const Matrix &a, const Matrix &b){ Matrix ans; ans.init(a.row(), b.col()); for(int i = 0; i < a.row();i++){ for(int j = 0; j < b.col();j++) ans.d[i][j] = inf; } for(int i = 0; i < a.row(); i++){ for(int j = 0; j < b.col();j++){ for(int k = 0; k < a.col();k++){ ans.d[i][j] = min(ans.d[i][j], a.d[i][k] + b.d[k][j]); } } } return ans; } Matrix t[N]; Matrix st[N][17]; void to_thic_cau(){ cin >> k >> n >> m >> q; ll lim = (n - 1) / k; for(int i = 0; i <= lim;i++){ t[i].init(k, k); for(int j = 0; j < k;j++){ for(int x = 0; x < k;x++) t[i].d[j][x] = inf; } } for(int i = 1; i <= m;i++){ ll u,v,w; cin >> u >> v >> w; t[v / k].d[u % k][v % k] = w; } for(int i = 0; i <= lim;i++) st[i][0] = t[i]; for(int j = 1; j <= lim;j++){ for(int i = 0; i + (1 << j) <= lim + 1;i++) st[i][j] = st[i][j-1] * st[i + (1 << (j - 1))][j-1]; } Matrix cur; while(q--){ ll a,b; cin >> a >> b; if(a / k == b / k){ cout << -1 << "\n"; continue; } ll l = a / k + 1, r = b / k; for(int i = 0; i < k;i++) cur.d[0][i] = inf; cur.d[0][a % k] = 0; ll d = r - l + 1; for(int i = 16; i >= 0;i--){ if(d & (1 << i)){ assert(l <= lim); cur = cur * st[l][i]; l += (1 << i); } } if(cur.d[0][b % k] >= 1e9){ cout << -1 << "\n"; } else cout << cur.d[0][b % k] << "\n"; } } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); ll tc = 1; //cin >> tc; while(tc--) to_thic_cau(); }
#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...