제출 #1227841

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1227841		thecyb	Toll (BOI17_toll)	C++17	100 / 100	80 ms	83576 KiB

toll

/*
    ==                     ==
                 <^\()/^>               <^\()/^>
                  \/  \/                 \/  \/
                   /__\      .  '  .      /__\
      ==            /\    .     |     .    /\            ==
   <^\()/^>       !_\/       '  |  '       \/_!       <^\()/^>
    \/  \/     !_/I_||  .  '   \'/   '  .  ||_I\_!     \/  \/
     /__\     /I_/| ||      -==C++==-      || |\_I\     /__\
     /_ \   !//|  | ||  '  .   /.\   .  '  || |  |\\!   /_ \
    (-   ) /I/ |  | ||       .  |  .       || |  | \I\ (=   )
     \__/!//|  |  | ||    '     |     '    || |  |  |\\!\__/
     /  \I/ |  |  | ||       '  .  '    *  || |  |  | \I/  \
    {_ __}  |  |  | ||                     || |  |  |  {____}
 _!__|= ||  |  |  | ||   *      +          || |  |  |  ||  |__!_
 _I__|  ||__|__|__|_||          A          ||_|__|__|__||- |__I_
 -|--|- ||--|--|--|-||       __/_\__  *    ||-|--|--|--||= |--|-
  |  |  ||  |  |  | ||      /\-'o'-/\      || |  |  |  ||  |  |
  |  |= ||  |  |  | ||     _||:<_>:||_     || |  |  |  ||= |  |
  |  |- ||  |  |  | || *  /\_/=====\_/\  * || |  |  |  ||= |  |
  |  |- ||  |  |  | ||  __|:_:_[I]_:_:|__  || |  |  |  ||- |  |
 _|__|  ||__|__|__|_||:::::::::::::::::::::||_|__|__|__||  |__|_
 -|--|= ||--|--|--|-||:::::::::::::::::::::||-|--|--|--||- |--|-
  jgs|- ||  |  |  | ||:::::::::::::::::::::|| |  |  |  ||= |  |
~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^~~~~~~~~~
*/
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ff first
#define ss second
#define pii pair<int, int>
#define mp make_pair
#define endl '\n'

namespace custom_cp {
void setIO(const std::string &s = "", const std::string &in = ".in",
           const std::string &out = ".out") {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
  if (!s.empty()) {
    freopen((s + in).c_str(), "r", stdin);
    freopen((s + out).c_str(), "w", stdout);
  }
}
} // namespace custom_cp

int dp[50000][17][5][5], ans[5][5], tmp[5][5];

void combine(int v[5][5], int x[5][5], int y[5][5], const int &k) {
  for (int a = 0; a < k; a++) {
    for (int b = 0; b < k; b++) {
      for (int c = 0; c < k; c++) {
        v[a][b] = std::min(v[a][b], x[a][c] + y[c][b]);
      }
    }
  }
}

int main() {
  custom_cp::setIO("");
  int k, n, m, o;
  std::cin >> k >> n >> m >> o;
  memset(dp, 0x3f, sizeof dp);
  for (int i = 0; i < m; i++) {
    int u, v, t;
    std::cin >> u >> v >> t;
    dp[u / k][0][u % k][v % k] = t;
  }

  for (int j = 1; j < 17; j++) {
    for (int i = 0; i + (1 << j) < (n - 1) / k + 1; i++) {
      combine(dp[i][j], dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1], k);
    }
  }

  for (int i = 0; i < o; i++) {
    int u, v;
    std::cin >> u >> v;
    memset(ans, 0x3f, sizeof ans);
    for (int i = 0; i < 5; i++)
      ans[i][i] = 0;
    for (int cur = u / k, end = v / k, b = 16; ~b; b--) {
      if (cur + (1 << b) <= end) {
        memset(tmp, 0x3f, sizeof tmp);
        combine(tmp, ans, dp[cur][b], k);
        memcpy(ans, tmp, sizeof ans);
        cur += (1 << b);
      }
    }
    std::cout << (ans[u % k][v % k] == 0x3f3f3f3f ? -1 : ans[u % k][v % k])
              << '\n';
  }
}

컴파일 시 표준 에러 (stderr) 메시지

toll.cpp: In function 'void custom_cp::setIO(const string&, const string&, const string&)':
toll.cpp:43:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     freopen((s + in).c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:44:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     freopen((s + out).c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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