#441527 (C++14) No.901 K-ary εxtrεεmε

提出ソース

結果

問題	No.901 K-ary εxtrεεmε
ユーザー	polylogK
提出日時	2020-03-09 04:05:29
言語	C++14 (gcc 12.3.0 + boost 1.83.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

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	WA	-
testcase_01	WA	-
testcase_02	WA	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	RE	-
testcase_08	RE	-
testcase_09	RE	-
testcase_10	RE	-
testcase_11	RE	-
testcase_12	RE	-
testcase_13	RE	-
testcase_14	RE	-
testcase_15	RE	-
testcase_16	RE	-
testcase_17	RE	-
testcase_18	RE	-
testcase_19	RE	-
testcase_20	RE	-
testcase_21	RE	-
testcase_22	RE	-
testcase_23	RE	-
testcase_24	RE	-
testcase_25	RE	-
testcase_26	RE	-
testcase_27	AC	629 ms 32,588 KB
testcase_28	AC	623 ms 32,580 KB
testcase_29	AC	621 ms 32,592 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
}

yukicoder

結果

テストケース

ソースコード