제출 #674857

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
674857		Valera_Grinenko	Toll (BOI17_toll)	C++17	100 / 100	89 ms	14076 KiB

toll

// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define make_unique(x) sort(all((x))); (x).resize(unique(all((x))) - (x).begin())
typedef long long ll;
typedef long double ld;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }
const int N = 50001;
int k, n, m, o;
vector<pair<pair<int, int>, int> > qq;
vector<pair<pair<int, int>, int> > g[N];
int ans[N];
ll dist[N][5][5];
void kek(int l, int r, vector<pair<pair<int, int>, int> >& curq) {
  vector<pair<pair<int, int>, int> > tol, tor, mid;
  int m = (l + r) / 2;
  for(int i = l; i <= r; i++)
    for(int a = 0; a < k; a++)
      for(int b = 0; b < k; b++)
        dist[i][a][b] = 1e18;
  for(int i = 0; i < k; i++)
    for(int j = 0; j < k; j++)
      dist[m][i][j] = (i == j ? 0 : 1e18);
  for(int i = m; i + 1 <= r; i++) {
    for(auto& edge : g[i])
      for(int st = 0; st < k; st++)
        umin(dist[i + 1][st][edge.fi.se], dist[i][st][edge.fi.fi] + edge.se);
  }
  for(int i = m; i - 1 >= l; i--) {
    for(auto& edge : g[i - 1])
      for(int fs = 0; fs < k; fs++)
        umin(dist[i - 1][fs][edge.fi.fi], dist[i][fs][edge.fi.se] + edge.se);
  }
  for(auto& x : curq)
    if(x.fi.se / k < m) tol.pb(x);
    else if(x.fi.fi / k > m) tor.pb(x);
    else {
      ll res = 1e18;
      for(int inter = 0; inter < k; inter++)
        umin(res, dist[x.fi.fi / k][inter][x.fi.fi % k] + dist[x.fi.se / k][inter][x.fi.se % k]);
      ans[x.se] = (res == 1e18 ? -1 : res);
    }
  if(l == r) return;
  if(!tol.empty()) kek(l, m - 1, tol);
  if(!tor.empty()) kek(m + 1, r, tor);
}
void solve() {
  cin >> k >> n >> m >> o;
  for(int i = 0; i < m; i++) {
    int a, b, t;
    cin >> a >> b >> t;
    g[a / k].pb(mp(mp(a % k, b % k), t));
  }
  for(int i = 0; i < o; i++) {
    ans[i] = -1;
    int a, b;
    cin >> a >> b;
    qq.pb(mp(mp(a, b), i));
  }
  kek(0, N / k, qq);
  for(int i = 0; i < o; i++) cout << ans[i] << '\n';
}
int main() {

  ios::sync_with_stdio(0); cin.tie(0);

  int t = 1;

  // cin >> t;

  while(t--) solve();

  return 0;
}
/*

*/

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44