結果
問題 | No.1442 I-wate Shortest Path Problem |
ユーザー | iaNTU |
提出日時 | 2021-01-30 20:37:50 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
RE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 6,492 bytes |
コンパイル時間 | 3,345 ms |
コンパイル使用メモリ | 230,412 KB |
実行使用メモリ | 36,040 KB |
最終ジャッジ日時 | 2024-10-11 12:23:08 |
合計ジャッジ時間 | 8,989 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 10 ms
13,824 KB |
testcase_01 | AC | 9 ms
13,952 KB |
testcase_02 | AC | 11 ms
14,592 KB |
testcase_03 | AC | 47 ms
15,872 KB |
testcase_04 | AC | 12 ms
14,592 KB |
testcase_05 | AC | 10 ms
14,464 KB |
testcase_06 | AC | 48 ms
16,128 KB |
testcase_07 | AC | 11 ms
14,336 KB |
testcase_08 | AC | 29 ms
15,872 KB |
testcase_09 | AC | 13 ms
15,104 KB |
testcase_10 | AC | 80 ms
16,000 KB |
testcase_11 | AC | 32 ms
16,128 KB |
testcase_12 | AC | 222 ms
33,332 KB |
testcase_13 | AC | 83 ms
32,384 KB |
testcase_14 | AC | 135 ms
32,632 KB |
testcase_15 | AC | 143 ms
33,152 KB |
testcase_16 | AC | 295 ms
33,024 KB |
testcase_17 | RE | - |
testcase_18 | RE | - |
testcase_19 | AC | 308 ms
33,392 KB |
testcase_20 | RE | - |
testcase_21 | RE | - |
testcase_22 | AC | 104 ms
35,328 KB |
testcase_23 | AC | 303 ms
36,040 KB |
testcase_24 | AC | 57 ms
32,824 KB |
testcase_25 | AC | 254 ms
34,608 KB |
testcase_26 | AC | 68 ms
33,136 KB |
ソースコード
// This solution is correct// O(nlgn + 2^k * k^2 * q) (With optimization, Should still TLE)#pragma GCC optimize("O3")// Exported by Exporter.exe// Included from Slow.cpp// Compile flags -Wall -Wextra -Wshadow -D_GLIBCXX_ASSERTIONS -DDEBUG -ggdb3 -fmax-errors=2#include <bits/stdc++.h>using namespace std;#define PB push_back#define F first#define S second#define MP make_pair#define MTP make_tupletypedef long long int ll;constexpr int kN = int(1E5 + 10);constexpr int kLgn = 17;// constexpr int kMod = 998244353;// constexpr int kInf = 0x3f3f3f3f;constexpr ll kInf = 0x3f3f3f3f3f3f3f3f;// constexpr double kPi = acos(-1);// constexpr double kEps = 1E-9;template <typename T> T ABS(T n) {return n >= 0 ? n : -n;}// Included from C:\Users\ianli\Desktop\CP\template\Various\Fast_IO.cppstatic inline char Get_Raw_Char() {static char buf[1 << 16], *p = buf, *end = buf;if (p == end) {if ((end = buf + fread(buf, 1, 1 << 16, stdin)) == buf) return '\0';p = buf;}return *p++;}static inline int Get_Digit() {char c = Get_Raw_Char();while (!isdigit(c)) c = Get_Raw_Char();return int(c - '0');}static inline int Get_PInt() {char c = Get_Raw_Char();int ret;while (!isdigit(c)) c = Get_Raw_Char();ret = int(c - '0');while (isdigit(c = Get_Raw_Char())) ret = ret * 10 + int(c - '0');return ret;}static inline int Get_Int() {char c = Get_Raw_Char();bool neg = false;int ret;while (!isdigit(c)) {if (c == '-') neg = true;c = Get_Raw_Char();}ret = int(c - '0');while (isdigit(c = Get_Raw_Char())) ret = ret * 10 + int(c - '0');if (neg) return -ret;return ret;}static inline long long int Get_ll() {char c = Get_Raw_Char();bool neg = false;long long int ret;while (!isdigit(c)) {if (c == '-') neg = true;c = Get_Raw_Char();}ret = int(c - '0');while (isdigit(c = Get_Raw_Char())) ret = ret * 10 + int(c - '0');if (neg) return -ret;return ret;}static inline long long int Get_Pll() {char c = Get_Raw_Char();long long int ret;while (!isdigit(c)) c = Get_Raw_Char();ret = int(c - '0');while (isdigit(c = Get_Raw_Char())) ret = ret * 10 + int(c - '0');return ret;}template <typename T> static inline void Read_P(T &n) {static_assert(is_integral<T>::value);char c = Get_Raw_Char();while (!isdigit(c)) c = Get_Raw_Char();n = int(c - '0');while (isdigit(c = Get_Raw_Char())) n = n * 10 + int(c - '0');return ;}template <typename T> static inline void Read(T &n) {static_assert(is_integral<T>::value);char c = Get_Raw_Char();bool neg = false;while (!isdigit(c)) {if (c == '-') neg = true;c = Get_Raw_Char();}n = int(c - '0');while (isdigit(c = Get_Raw_Char())) n = n * 10 + int(c - '0');if (neg) n = -n;return ;}template <typename T> static inline void Read_Digit(T &n) {static_assert(is_integral<T>::value);char c = Get_Raw_Char();while (!isdigit(c)) c = Get_Raw_Char();n = int(c - '0');return ;}template <typename T, typename... Targs> static inline void Read(T &n, Targs&... Fargs) {Read(n);return Read(Fargs...);}template <typename T, typename... Targs> static inline void Read_Digit(T &n, Targs&... Fargs) {Read_Digit(n);return Read_Digit(Fargs...);}template <typename T, typename... Targs> static inline void Read_P(T &n, Targs&... Fargs) {Read_P(n);return Read_P(Fargs...);}// End of C:\Users\ianli\Desktop\CP\template\Various\Fast_IO.cppint m[10], p[10], x[10][kN], u[kN], v[kN], dep[kN];ll ans[kN], fa[kLgn][kN], dis[10][kN], dis_color[10][10], dis_color_tmp[10][10];vector<pair<int, int>> graph[kN];void dfs(int cur, int from) {for (pair<int, int> i : graph[cur]) if (i.F != from) {fa[0][i.F] = cur;dis[0][i.F] = dis[0][cur] + i.S;dep[i.F] = dep[cur] + 1;dfs(i.F, cur);}return ;}int LCA(int l, int r) {if (dep[l] < dep[r]) swap(l, r);for (int i = kLgn - 1; i >= 0; i--) if (dep[fa[i][l]] >= dep[r]) l = fa[i][l];if (l == r) return l;for (int i = kLgn - 1; i >= 0; i--) if (fa[i][l] != fa[i][r]) l = fa[i][l], r = fa[i][r];return fa[0][l];}int main() {//ios::sync_with_stdio(false);//cin.tie(0);//freopen("file_name", "r", stdin);//freopen("file_name", "w", stdout);//fstream input, output;//input.open("file_name", ios::in);//output.open("file_name", ios::out);int n, k, q;Read_P(n, k);for (int i = 2; i <= n; i++) {int l, r, c;Read_P(l, r, c);graph[l].PB(MP(r, c));graph[r].PB(MP(l, c));}for (int i = 1; i <= k; i++) {Read_P(m[i], p[i]);for (int j = 1; j <= m[i]; j++) Read_P(x[i][j]);}Read_P(q);for (int i = 1; i <= q; i++) Read_P(u[i], v[i]);memset(dis, 0x3f, sizeof(dis));memset(dis_color, 0x3f, sizeof(dis_color));dis[0][1] = 0;dfs(1, 1);fa[0][1] = 1;for (int i = 1; i < kLgn; i++) {#pragma unrollfor (int j = 1; j <= n; j++) fa[i][j] = fa[i - 1][fa[i - 1][j]];}#pragma unrollfor (int i = 1; i <= q; i++) ans[i] = dis[0][u[i]] + dis[0][v[i]] - dis[0][LCA(u[i], v[i])] * 2;for (int i = 1; i <= k; i++) {priority_queue<ll, vector<ll>, greater<ll>> pq;for (int j = 1; j <= m[i]; j++) pq.push(x[i][j]);#pragma unrollfor (int j = 1; j <= m[i]; j++) dis[i][x[i][j]] = 0;while (!pq.empty()) {int cur = pq.top() & 0xfffff;ll ndis = pq.top() >> 20;pq.pop();if (ndis > dis[i][cur]) continue;for (pair<int, int> j : graph[cur]) if (dis[i][j.F] > ndis + j.S)pq.push((dis[i][j.F] = ndis + j.S) << 20 | j.F);}for (int j = i + 1; j <= k; j++) for (int c = 1; c <= m[j]; c++)dis_color[i][j] = min(dis_color[i][j], dis[i][x[j][c]]);}for (int i = 1; i <= k; i++) dis_color[i][i] = 0;for (int i = 1; i <= k; i++) for (int j = i + 1; j <= k; j++) dis_color[j][i] = dis_color[i][j];int tot = 1 << k;for (int mask = 1; mask < tot; mask++) {vector<int> vec;for (int i = 1; i <= k; i++) if (mask & (1 << (i - 1))) vec.PB(i);memcpy(dis_color_tmp, dis_color, sizeof(dis_color));//for (int i : vec) for (int j : vec) dis_color_tmp[i][j] = dis_color[i][j];for (int c : vec) for (int i : vec) for (int j : vec)dis_color_tmp[i][j] = min(dis_color_tmp[i][j], dis_color_tmp[i][c] + dis_color_tmp[c][j]);ll tmp = 0;for (int i : vec) tmp += p[i];for (int i = 1; i <= q; i++) for (int a : vec) for (int b : vec)ans[i] = min(ans[i], dis[a][u[i]] + dis[b][v[i]] + dis_color_tmp[a][b] + tmp);}for (int i = 1; i <= q; i++) printf("%lld\n", ans[i]);//input.close();//output.close();}// End of Slow.cpp