結果

問題 No.1442 I-wate Shortest Path Problem
ユーザー iaNTUiaNTU
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// 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_tuple
typedef 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.cpp
static 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.cpp
int 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 unroll
for (int j = 1; j <= n; j++) fa[i][j] = fa[i - 1][fa[i - 1][j]];
}
#pragma unroll
for (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 unroll
for (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
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0