Submission #697121

#TimeUsernameProblemLanguageResultExecution timeMemory
697121AmirElarbiToll (BOI17_toll)C++14
100 / 100
117 ms82020 KiB
#include <bits/stdc++.h> #define vi vector<int> #define ve vector #define ll long long #define vf vector<float> #define vll vector<pair<ll,ll>> #define ii pair<int,int> #define pll pair<ll,ll> #define vvi vector<vi> #define vii vector<ii> #define gii greater<ii> #define pb push_back #define mp make_pair #define fi first #define se second #define INF 1e9 #define eps 1e-7 #define eps1 1e-2 #define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); #define MAX_A 2e5+5 using namespace std; const int MOD = 1e9+7; const int nax = 5e4+5; const int nax2 = 20; typedef complex<int> Point; using cd = complex<double>; int k,n,m,o, dat[5][5][32][nax]; int ans[5][5],cnt[5][5]; void combine(int l, int lev){ for(int i = 0; i < k; i++) for(int j = 0; j < k; j++){ for (int z = 0; z < k; ++z) { dat[i][j][lev][l] = min(dat[i][j][lev][l], dat[i][z][lev-1][l] + dat[z][j][lev-1][l+(1 << (lev-1))]); } } } int main() { optimise; cin >> k >> n >> m >> o; for (int i = 0; i < k; ++i) for (int j = 0; j < k; ++j) for (int a = 0; a < 25; ++a) for(int b = 0; b < n; b++) dat[i][j][a][b] = INF; for (int i = 0; i < m; ++i) { int a,b,c; cin >> a >> b >> c; dat[a % k][b % k][0][a / k] = c; } for (int i = 1; i < 25; ++i) { for (int j = 0; j + (1 << i) < (n+k-1)/k; ++j) { combine(j, i); } } while(o--){ int a,b; cin >> a >> b; if(a == b) cout << 0 << endl; else if(a/k >= b/k) cout << -1 << endl; else { int cur = a/k; for(int i = 0; i < k; i++) for(int j = 0; j < k; j++) if(i == j) ans[i][j] = 0; else ans[i][j] = INF; for (int lvl = 20; lvl >= 0; --lvl) { if(cur + (1 << lvl) <= b/k){ for(int i = 0; i < k; i++) for(int j = 0; j < k; j++) cnt[i][j] = INF; for(int i = 0; i < k; i++) for(int j = 0; j < k; j++){ for (int z = 0; z < k; ++z) { cnt[i][j] = min(cnt[i][j], ans[i][z] + dat[z][j][lvl][cur]); } } memcpy(ans, cnt, sizeof ans); cur += (1 << lvl); } } if(ans[a%k][b%k] >= INF) cout << -1 << endl; else cout << ans[a%k][b%k] << endl; } } }
#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...