Submission #1215653

#TimeUsernameProblemLanguageResultExecution timeMemory
1215653sasdeToll (BOI17_toll)C++20
0 / 100
157 ms166796 KiB
//Huyduocdithitp #include <bits/stdc++.h> typedef long long ll; #define endl '\n' #define yes cout<<"YES"<<endl; #define no cout<<"NO"<<endl; #define fi first #define se second #define pii pair<ll, ll> #define inf 1e18 #define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); #define MP make_pair #define TASK "ghuy4g" #define start if(fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin);freopen(TASK".out","w",stdout);} #define LOG 15 #define N 500005 using namespace std; struct Node { ll m[5][5]; Node () { for (int i = 0; i < 5; i ++) { for (int j = 0; j < 5; j ++) { m[i][j] = inf; } } } }; ll k, n, m, o; Node dp[50005][LOG + 2]; Node combine(Node L, Node R) { Node res; for (int i = 0; i < k; i ++) { for (int j = 0; j < k; j ++) { for (int l = 0; l < k; l ++) { if (L.m[i][j] != inf && R.m[j][l] != inf) { res.m[i][l] = min(res.m[i][l], L.m[i][j] + R.m[j][l]); } } } } return res; } void prepare() { for (int j = 1; j <= LOG; j ++) { for (int i = 0; i <= n / k; i ++) { // cout <<i+(1<<(j-1))<<'\n'; dp[i][j] = combine(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]); } } } signed main(void) { faster; cin >> k >> n >> m >> o; for (int i = 1; i <= m; i ++) { ll u, v, w; cin >> u >> v >> w; if (u > v) swap(u, v); ll x = u % k, y = v % k; dp[u / k][0].m[x][y] = min(dp[u / k][0].m[x][y], w); } prepare(); for (int id = 1; id <= o; id ++) { ll u, v; cin >> u >> v; // dp[a][b][x][y] ll a = u / k, b = v / k, x = u % k, y = v % k; if (a >= b) { cout << -1 << endl; continue; } ll dis = b - a; Node res; for (int j = 0; j < k; j ++) { res.m[j][j] = 0; } for (int j = LOG; j >= 0; j --) { if (dis >= (1 << j)) { dis -= (1 << j); res = combine(res, dp[a][j]); a += (1 << j); } } ll kq = res.m[x][y]; if (kq == inf) { cout << -1 << endl; continue; } cout << kq << 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...