結果

問題 No.901 K-ary εxtrεεmε
ユーザー polylogKpolylogK
提出日時 2019-09-19 23:22:36
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 853 ms / 3,000 ms
コード長 8,356 bytes
コンパイル時間 2,925 ms
コンパイル使用メモリ 205,108 KB
実行使用メモリ 32,812 KB
最終ジャッジ日時 2024-10-04 06:26:01
合計ジャッジ時間 19,521 ms
ジャッジサーバーID
(参考情報)
judge2 / judge5
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 258 ms
32,812 KB
testcase_01 AC 1 ms
6,816 KB
testcase_02 AC 6 ms
6,816 KB
testcase_03 AC 6 ms
6,820 KB
testcase_04 AC 7 ms
6,820 KB
testcase_05 AC 6 ms
6,816 KB
testcase_06 AC 7 ms
6,816 KB
testcase_07 AC 739 ms
30,304 KB
testcase_08 AC 756 ms
30,116 KB
testcase_09 AC 816 ms
30,296 KB
testcase_10 AC 748 ms
30,112 KB
testcase_11 AC 770 ms
30,140 KB
testcase_12 AC 655 ms
30,100 KB
testcase_13 AC 643 ms
30,124 KB
testcase_14 AC 644 ms
30,236 KB
testcase_15 AC 651 ms
30,244 KB
testcase_16 AC 636 ms
30,228 KB
testcase_17 AC 845 ms
30,140 KB
testcase_18 AC 834 ms
30,120 KB
testcase_19 AC 829 ms
30,132 KB
testcase_20 AC 853 ms
30,116 KB
testcase_21 AC 845 ms
30,272 KB
testcase_22 AC 455 ms
30,272 KB
testcase_23 AC 436 ms
30,176 KB
testcase_24 AC 460 ms
30,176 KB
testcase_25 AC 438 ms
30,224 KB
testcase_26 AC 446 ms
30,200 KB
testcase_27 AC 571 ms
30,264 KB
testcase_28 AC 560 ms
30,240 KB
testcase_29 AC 560 ms
30,116 KB
権限があれば一括ダウンロードができます

ソースコード

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

#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;
template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
// build: you have to run it before you use
// for_each: process [l, r]
// for_each_edge: process [l, r]
// distance: returns the dist (l, r)
class heavy_light_decomposition {
using size_type = size_t;
using F = std::function<void (int, int)>;
public:
std::vector<std::vector<int>> g;
std::vector<int> vid, inv;
private:
std::vector<int> head, sz, heavy, par, dep, type;
void dfs(int root) {
using P = std::pair<int, int>;
par[root] = -1;
dep[root] = 0;
std::stack<P> st;
st.push({root, 0});
while(!st.empty()) {
int v = st.top().first;
int & i = st.top().second;
if(i < g[v].size()) {
int u = g[v][i++];
if(u == par[v]) continue;
par[u] = v;
dep[u] = dep[v] + 1;
st.push({u, 0});
} else {
st.pop();
int tmp = 0;
for(auto e: g[v]) {
if(e == par[v]) continue;
sz[v] += sz[e];
if(tmp < sz[e]) {
tmp = sz[e];
heavy[v] = e;
}
}
}
}
}
void bfs(int root, int c, int & k) {
std::queue<int> qu({root});
while(!qu.empty()) {
int h = qu.front(); qu.pop();
for(int v = h; v != -1; v = heavy[v]) {
type[v] = c;
vid[v] = k++;
inv[vid[v]] = v;
head[v] = h;
for(int e: g[v])
if(e != par[v] and e != heavy[v]) qu.push(e);
}
}
}
public:
heavy_light_decomposition() {}
heavy_light_decomposition(int n) :
g(n), vid(n, -1), head(n), sz(n, 1), heavy(n, -1),
par(n), dep(n), inv(n), type(n) {}
void add_edge(int a, int b) {
g[a].push_back(b);
g[b].push_back(a);
}
void build(std::vector<int> rs = std::vector<int>(1, 0)) {
int c = 0, k = 0;
for(int r: rs) {
dfs(r);
bfs(r, c++, k);
}
}
int lca(int u, int v) {
while(true) {
if(vid[u] > vid[v]) std::swap(u, v);
if(head[u] == head[v]) return u;
v = par[head[v]];
}
}
void for_each(int u, int v, const F & f) {
while(true) {
if(vid[u] > vid[v]) std::swap(u, v);
f(std::max(vid[head[v]], vid[u]), vid[v]);
if(head[u] != head[v]) v = par[head[v]];
else break;
}
}
void for_each_edge(int u, int v, const F & f) {
while(true) {
if(vid[u] > vid[v]) std::swap(u, v);
if(head[u] != head[v]) {
f(vid[head[v]], vid[v]);
v = par[head[v]];
} else {
if(u != v) f(vid[u] + 1, vid[v]);
break;
}
}
}
int distance(int u, int v) {
return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}
};
template<typename Monoid, typename OperatorMonoid = Monoid>
class lazy_segment_tree {
using value_type = Monoid;
using operator_type = OperatorMonoid;
using size_type = size_t;
using F = std::function<value_type (value_type, value_type)>;
using G = std::function<value_type (value_type, operator_type, int, int)>;
using H = std::function<operator_type (operator_type, operator_type)>;
size_type size_;
size_type height_;
F f;
G g;
H h;
value_type id;
operator_type id_op;
std::vector<value_type> data;
std::vector<operator_type> lazy;
std::vector<size_type> depth;
const size_type get_height(const size_type& size) const {
size_type height = 1;
while(1 << height < size) height++;
return height;
}
const size_type base_size() const {
return 1 << height_;
}
const value_type reflect(const size_type & k) {
if(lazy[k] == id_op) return data[k];
int l = (k - (1 << depth[k])) * (base_size() >> depth[k]);
int r = l + (base_size() >> depth[k]);
return g(data[k], lazy[k], l, r);
}
void eval(const size_type & k) {
if(lazy[k] == id_op) return;
lazy[k << 1 ^ 0] = h(lazy[k << 1 ^ 0], lazy[k]);
lazy[k << 1 ^ 1] = h(lazy[k << 1 ^ 1], lazy[k]);
data[k] = reflect(k);
lazy[k] = id_op;
}
void thrust(const size_type & k) {
for(int i = height_; i; i--) eval(k >> i);
}
void recalc(size_type k) {
while(k >>= 1) data[k] = f(reflect(k << 1 ^ 0), reflect(k << 1 ^ 1));
}
public:
lazy_segment_tree() {}
lazy_segment_tree(int n, const F & f, const G & g, const H & h, const value_type & id, const operator_type & id_op) :
size_(n), f(f), g(g), h(h), id(id), id_op(id_op) {
height_ = get_height(size_);
data.assign(base_size() << 1, id);
lazy.assign(base_size() << 1, id_op);
depth.assign(base_size() << 1, 0);
for(int i = 0; i < height_ + 1; i++)
for(int j = (1 << i); j < (1 << (i + 1)); j++)
depth[j] = i;
}
void update(size_type a, size_type b, operator_type x) {
thrust(a += base_size());
thrust(b += base_size() - 1);
for(size_type l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
if(l & 1) lazy[l] = h(lazy[l], x), l++;
if(r & 1) --r, lazy[r] = h(lazy[r], x);
}
recalc(a);
recalc(b);
}
void change(size_type k, const value_type x) {
thrust(k += base_size());
data[k] = x;
lazy[k] = id_op;
recalc(k);
}
const value_type fold(size_type a, size_type b) {
thrust(a += base_size());
thrust(b += base_size() - 1);
value_type left_value = id;
value_type right_value = id;
for(size_type l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
if(l & 1) left_value = f(left_value, reflect(l++));
if(r & 1) right_value = f(reflect(--r), right_value);
}
return f(left_value, right_value);
}
const value_type operator[](const size_type & k) {
return fold(k, k + 1);
}
};
struct node {
int used;
int depth;
int label;
int depth_all;
int label_all;
node() : used(1), depth(-1), label(-1), depth_all(-1), label_all(-1) {}
node(int used, int depth, int label, int depth_all, int label_all) : used(used), depth(depth), label(label), depth_all(depth_all), label_all
        (label_all) {}
void print() {
printf("used = %d\n", used);
printf("depth = %d\n", depth);
printf("label = %d\n", label);
printf("depth_all = %d\n", depth_all);
printf("label_all = %d\n", label_all);
}
};
int main() {
int n; scanf("%d", &n);
std::vector<std::vector<std::pair<int, i64>>> g(n);
heavy_light_decomposition hld(n);
for(int i = 0; i < n - 1; i++) {
int a, b, c; scanf("%d%d%d", &a, &b, &c);
g[a].push_back({b, c});
g[b].push_back({a, c});
hld.add_edge(a, b);
}
hld.build();
std::vector<i64> dist(n), depth(n);
auto dfs = [&](auto && dfs, int v, int par) -> void {
for(auto e: g[v]) {
if(e.first == par) continue;
dist[e.first] = dist[v] + e.second;
depth[e.first] = depth[v] + 1;
dfs(dfs, e.first, v);
}
};
dfs(dfs, 0, -1);
auto calc = [dist, &hld](int u, int v) {
return dist[u] + dist[v] - 2LL * dist[hld.lca(u, v)];
};
auto f = [](node a, node b) {
node ret;
ret.used = 0;
if(a.depth_all > b.depth_all) {
ret.label_all = a.label_all;
ret.depth_all = a.depth_all;
} else {
ret.label_all = b.label_all;
ret.depth_all = b.depth_all;
}
int A = a.label, B = a.depth, C = b.label, D = b.depth;
if(a.used) {
A = a.label_all;
B = a.depth_all;
}
if(b.used) {
C = b.label_all;
D = b.depth_all;
}
if(B > D) {
ret.label = A;
ret.depth = B;
} else {
ret.label = C;
ret.depth = D;
}
return ret;
};
auto gg = [](node a, int b, int l, int r) {
if(b) {
a.used = 1;
a.depth = a.depth_all;
a.label = a.label_all;
} else {
a.used = 0;
a.depth = -1;
a.label = -1;
}
return a;
};
auto h = [](int a, int b) { return b; };
lazy_segment_tree<node, int> A(n, f, gg, h, node(), -1);
for(int i = 0; i < n; i++) {
int v = hld.inv[i];
A.change(i, node(0, -1, -1, depth[v], v));
}
auto kiri = [&A](int l, int r) {
A.update(l, r + 1, 1);
};
auto irik = [&A](int l, int r) {
A.update(l, r + 1, 0);
};
int q; scanf("%d", &q);
while(q--) {
int k; scanf("%d", &k);
std::vector<int> vec(k);
for(int i = 0; i < k; i++) scanf("%d", &vec[i]);
i64 ans = 0;
int c = vec.front();
for(auto v: vec) {
node tmp = node();
auto tanpo = [&](int l, int r) {
tmp = f(tmp, A.fold(l, r + 1));
};
hld.for_each(0, v, tanpo);
if(tmp.depth == -1) {
ans += calc(v, c);
hld.for_each(v, c, kiri);
c = hld.lca(v, c);
} else {
int u = tmp.label;
ans += calc(u, v);
hld.for_each(u, v, kiri);
}
}
A.update(0, n, 0);
printf("%lld\n", ans);
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0