結果
問題 | No.1607 Kth Maximum Card |
ユーザー | fastmath |
提出日時 | 2021-07-16 22:32:13 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,465 ms / 3,500 ms |
コード長 | 4,124 bytes |
コンパイル時間 | 1,522 ms |
コンパイル使用メモリ | 143,844 KB |
実行使用メモリ | 31,988 KB |
最終ジャッジ日時 | 2023-09-20 14:50:41 |
合計ジャッジ時間 | 14,635 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 9 ms
9,668 KB |
testcase_01 | AC | 9 ms
9,616 KB |
testcase_02 | AC | 10 ms
9,544 KB |
testcase_03 | AC | 10 ms
9,544 KB |
testcase_04 | AC | 10 ms
9,668 KB |
testcase_05 | AC | 9 ms
9,588 KB |
testcase_06 | AC | 10 ms
9,868 KB |
testcase_07 | AC | 10 ms
9,612 KB |
testcase_08 | AC | 1,227 ms
29,988 KB |
testcase_09 | AC | 863 ms
26,500 KB |
testcase_10 | AC | 1,184 ms
30,532 KB |
testcase_11 | AC | 81 ms
14,156 KB |
testcase_12 | AC | 794 ms
25,524 KB |
testcase_13 | AC | 60 ms
12,836 KB |
testcase_14 | AC | 79 ms
14,116 KB |
testcase_15 | AC | 401 ms
27,908 KB |
testcase_16 | AC | 65 ms
13,648 KB |
testcase_17 | AC | 27 ms
10,584 KB |
testcase_18 | AC | 231 ms
23,520 KB |
testcase_19 | AC | 142 ms
18,024 KB |
testcase_20 | AC | 195 ms
20,180 KB |
testcase_21 | AC | 208 ms
21,636 KB |
testcase_22 | AC | 641 ms
29,456 KB |
testcase_23 | AC | 626 ms
29,720 KB |
testcase_24 | AC | 160 ms
16,328 KB |
testcase_25 | AC | 96 ms
13,484 KB |
testcase_26 | AC | 115 ms
14,272 KB |
testcase_27 | AC | 173 ms
16,672 KB |
testcase_28 | AC | 136 ms
15,128 KB |
testcase_29 | AC | 497 ms
22,016 KB |
testcase_30 | AC | 1,465 ms
30,676 KB |
testcase_31 | AC | 471 ms
20,624 KB |
testcase_32 | AC | 201 ms
30,964 KB |
testcase_33 | AC | 205 ms
31,988 KB |
testcase_34 | AC | 197 ms
30,632 KB |
testcase_35 | AC | 199 ms
31,104 KB |
ソースコード
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cmath> #include <vector> #include <set> #include <map> #include <unordered_set> #include <unordered_map> #include <queue> #include <ctime> #include <cassert> #include <complex> #include <string> #include <cstring> #include <chrono> #include <random> #include <bitset> #include <fstream> #include <array> using namespace std; #define int long long #define ii pair <int, int> #define app push_back #define all(a) a.begin(), a.end() #define bp __builtin_popcountll #define ll long long #define mp make_pair #define x first #define y second #define Time (double)clock()/CLOCKS_PER_SEC #define debug(x) std::cerr << #x << ": " << x << '\n'; #define FORI(i,a,b) for (int i = (a); i < (b); ++i) #define FOR(i,a) FORI(i,0,a) #define ROFI(i,a,b) for (int i = (b)-1; i >= (a); --i) #define ROF(i,a) ROFI(i,0,a) #define rep(a) FOR(_,a) #define each(a,x) for (auto& a: x) #define FORN(i, n) FORI(i, 1, n + 1) using vi = vector<int>; template <typename T> std::istream& operator >>(std::istream& input, std::pair <T, T> & data) { input >> data.x >> data.y; return input; } template <typename T> std::istream& operator >>(std::istream& input, std::vector<T>& data) { for (T& x : data) input >> x; return input; } template <typename T> std::ostream& operator <<(std::ostream& output, const pair <T, T> & data) { output << "(" << data.x << "," << data.y << ")"; return output; } template <typename T> std::ostream& operator <<(std::ostream& output, const std::vector<T>& data) { for (const T& x : data) output << x << " "; return output; } std::ostream& operator <<(std::ostream& output, const __int128 &x) { __int128 n = x; if (n == 0) { output << "0"; return output; } if (n < 0) { n = -n; output << "-"; } string s; while (n) { s += '0' + (n%10); n /= 10; } reverse(all(s)); cout << s; return output; } ll div_up(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up ll div_down(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down ll math_mod(ll a, ll b) { return a - b * div_down(a, b); } #define tcT template<class T #define tcTU tcT, class U tcT> using V = vector<T>; tcT> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; } // set a = min(a,b) tcT> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; } ll gcd(ll a, ll b) { while (b) { tie(a, b) = mp(b, a % b); } return a; } int Bit(int mask, int bit) { return (mask >> bit) & 1; } const int N = 2e5+7; V <ii> g[N]; int dist[N]; signed main() { #ifdef LOCAL #else #define endl '\n' ios_base::sync_with_stdio(0); cin.tie(0); #endif int n, m, k; cin >> n >> m >> k; V <vi> ed; rep (m) { int u, v, c; cin >>u >>v>>c; ed.app({u, v, c}); } auto check = [&] (int key) { FOR (i, N) { g[i].clear(); dist[i] = N; } //k-th min <= key each (e, ed) { int u = e[0], v = e[1]; if (e[2] <= key) { g[u].app(mp(v, 0)); g[v].app(mp(u, 0)); } else { g[u].app(mp(v, 1)); g[v].app(mp(u, 1)); } } deque <int> q; dist[1] = 0; q.push_back(1); while (q.size()) { int u = q.front(); q.pop_front(); each (e, g[u]) { int v = e.x, c = e.y; if (ckmin(dist[v], dist[u] + c)) { if (c == 0) { q.push_front(v); } else { q.push_back(v); } } } } return dist[n] < k; }; int l = -1, r = N; while (l < r - 1) { int m = (l + r) / 2; if (check(m)) { r = m; } else { l = m; } } cout << r << endl; }