結果
| 問題 | No.901 K-ary εxtrεεmε |
| ユーザー |
 polylogK
|
| 提出日時 | 2020-03-09 04:05:29 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,502 bytes |
| コンパイル時間 | 2,937 ms |
| コンパイル使用メモリ | 201,984 KB |
| 実行使用メモリ | 49,560 KB |
| 最終ジャッジ日時 | 2024-11-07 20:39:30 |
| 合計ジャッジ時間 | 21,179 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | WA * 1 |
| other | AC * 3 WA * 6 RE * 20 |
ソースコード
#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...));}class heavy_light_decomposition {public:using i32 = std::int_fast32_t;using u32 = std::uint_fast32_t;std::vector<std::vector<u32>> g;std::vector<u32> edge_u, edge_v, size, et, in, out, head;std::vector<i32> parent, heavy;private:void calc_size(u32 v) {size[v] = 1;for(int id: g[v]) {int to = edge_u[id] ^ edge_v[id] ^ v;if(to == parent[v]) continue;parent[to] = v;calc_size(to);size[v] += size[to];if(heavy[v] == -1 or size[heavy[v]] < size[to]) heavy[v] = to;}}void calc_et(u32 v) {in[v] = et.size();et.push_back(v);if(heavy[v] != -1) {calc_et(heavy[v]);head[heavy[v]] = head[v];}for(int id: g[v]) {int to = edge_u[id] ^ edge_v[id] ^ v;if(to == parent[v] or to == heavy[v]) continue;head[to] = to;calc_et(to);}out[v] = et.size();}template<class F>void path(u32 x, u32 y, F& process, bool edge) const {std::vector<std::pair<u32, u32>> l, r;while(true) {if(in[x] > in[y]) {std::swap(x, y);l.swap(r);}if(head[x] == head[y]) {l.emplace_back(in[x] + !!edge, in[y] + 1);break;}l.emplace_back(in[head[y]], in[y] + 1);y = parent[head[y]];}for(auto e: l) process(e.first, e.second);for(auto e: r) process(e.first, e.second);}template<class F>void subtree(u32 v, F& process, bool edge) const {process(in[v] + !!edge, out[v]);}public:heavy_light_decomposition() = default;heavy_light_decomposition(heavy_light_decomposition&&) = default;heavy_light_decomposition(const heavy_light_decomposition &) = default;heavy_light_decomposition(int n): g(n), size(n), in(n), out(n), parent(n, -1), heavy(n, -1), head(n) {}void add_edge(int x, int y) {g[x].push_back(edge_u.size());g[y].push_back(edge_v.size());edge_u.push_back(x);edge_v.push_back(y);}void build(u32 root = 0) {calc_size(root);calc_et(root);}u32 lca(u32 x, u32 y) const {while(true) {if(in[x] > in[y]) std::swap(x, y);if(head[x] == head[y]) return x;y = parent[head[y]];}}template<class F>void path_node(u32 x, u32 y, const F& process) const { path(x, y, process, false); }template<class F>void path_edge(u32 x, u32 y, const F& process) const { path(x, y, process, true); }template<class F>void path(u32 x, u32 y, const F& process) const { path(x, y, process, false); }template<class F>void subtree_node(u32 v, const F& process) const { subtree(v, process, false); }template<class F>void subtree_edge(u32 v, const F& process) const { subtree(v, process, true); }template<class F>void subtree(u32 v, const F& process) const { subtree(v, process, false); }u32 index_node(u32 v) const { return in[v]; };u32 index_edge(u32 x, u32 y) const { return std::max(in[x], in[y]); };u32 index(u32 v) const { return in[v]; };const u32 operator[](u32 k) const { return in[k]; }};using namespace std;template <typename T,typename E>struct SegmentTree{using F = function<T(T,T)>;using G = function<T(T,E)>;using H = function<E(E,E)>;int n,height;F f;G g;H h;T ti;E ei;vector<T> dat;vector<E> laz;SegmentTree(F f,G g,H h,T ti,E ei):f(f),g(g),h(h),ti(ti),ei(ei){}void init(int n_){n=1;height=0;while(n<n_) n<<=1,height++;dat.assign(2*n,ti);laz.assign(2*n,ei);}void build(const vector<T> &v){int n_=v.size();init(n_);for(int i=0;i<n_;i++) dat[n+i]=v[i];for(int i=n-1;i;i--)dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);}inline T reflect(int k){return laz[k]==ei?dat[k]:g(dat[k],laz[k]);}inline void eval(int k){if(laz[k]==ei) return;laz[(k<<1)|0]=h(laz[(k<<1)|0],laz[k]);laz[(k<<1)|1]=h(laz[(k<<1)|1],laz[k]);dat[k]=reflect(k);laz[k]=ei;}inline void thrust(int k){for(int i=height;i;i--) eval(k>>i);}inline void recalc(int k){while(k>>=1)dat[k]=f(reflect((k<<1)|0),reflect((k<<1)|1));}void update(int a,int b,E x){thrust(a+=n);thrust(b+=n-1);for(int l=a,r=b+1;l<r;l>>=1,r>>=1){if(l&1) laz[l]=h(laz[l],x),l++;if(r&1) --r,laz[r]=h(laz[r],x);}recalc(a);recalc(b);}void set_val(int a,T x){thrust(a+=n);dat[a]=x;laz[a]=ei;recalc(a);}T query(int a,int b){thrust(a+=n);thrust(b+=n-1);T vl=ti,vr=ti;for(int l=a,r=b+1;l<r;l>>=1,r>>=1) {if(l&1) vl=f(vl,reflect(l++));if(r&1) vr=f(reflect(--r),vr);}return f(vl,vr);}};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) {}};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) {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; };SegmentTree<node, int> A(f, gg, h, node(), -1);A.init(n);for(int i = 0; i < n; i++) {int v = hld.index(i);A.set_val(i, node(0, -1, -1, depth[v], v));}auto kiri = [&A](int l, int r) {A.update(l, r, 1);};auto irik = [&A](int l, int r) {A.update(l, r, 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.query(l, r));};hld.path(0, v, tanpo);if(tmp.depth == -1) {ans += calc(v, c);hld.path(v, c, kiri);c = hld.lca(v, c);} else {int u = tmp.label;ans += calc(u, v);hld.path(u, v, kiri);}}A.update(0, n, 0);printf("%lld\n", ans);}return 0;}