#272710 (C++14) No.399 動的な領主

提出ソース

結果

問題	No.399 動的な領主
ユーザー	pazzle1230
提出日時	2018-07-14 01:24:12
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	686 ms / 2,000 ms
コード長	5,048 bytes
コンパイル時間	2,213 ms
コンパイル使用メモリ	192,376 KB
実行使用メモリ	20,736 KB
最終ジャッジ日時	2024-10-09 05:53:36
合計ジャッジ時間	9,299 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	2 ms 5,248 KB
testcase_04	AC	4 ms 5,248 KB
testcase_05	AC	42 ms 5,248 KB
testcase_06	AC	676 ms 19,712 KB
testcase_07	AC	654 ms 19,840 KB
testcase_08	AC	663 ms 19,840 KB
testcase_09	AC	663 ms 19,840 KB
testcase_10	AC	5 ms 5,248 KB
testcase_11	AC	33 ms 5,248 KB
testcase_12	AC	490 ms 20,480 KB
testcase_13	AC	450 ms 20,480 KB
testcase_14	AC	179 ms 20,736 KB
testcase_15	AC	264 ms 20,688 KB
testcase_16	AC	341 ms 20,608 KB
testcase_17	AC	686 ms 19,812 KB
testcase_18	AC	650 ms 19,840 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

class HLDecomposition{
private:
	vector<vector<int32>> G;
	vector<int32> vid, inv, dep, hvy, par, typ, sub, head;
	int32 n, pos;
public:
	HLDecomposition(){}
	HLDecomposition(int32 n):
		n(n), pos(0), G(n), vid(n), inv(n), dep(n, -1),
		hvy(n, -1), par(n), typ(n), sub(n, 1), head(n){}

	void add_edge(int32 u, int32 v){
		G[u].push_back(v);
		G[v].push_back(u);
	}

	void build(){
		int32 type = 0;
		for(int32 i = 0;i < n;i++){
			if(dep[i] == -1){
				dfs(i);
				bfs(i, type++);
			}
		}
	}

	void dfs(int32 v){
		using T = pair<int32, int32>;
		dep[v] = 0;
		par[v] = -1;
		stack<T> st;
		st.emplace(v, 0);
		while(st.size()){
			v = st.top().first;
			int32 &i = st.top().second;
			if(i<G[v].size()){
				int32 u = G[v][i++];
				if(u == par[v]) continue;
				par[u] = v;
				dep[u] = dep[v]+1;
				st.emplace(u, 0);
			}else{
				st.pop();
				for(int32 u : G[v]){
					if(u == par[v]) continue;
					sub[v] += sub[u];
					if(hvy[v] == -1 || sub[u] > sub[hvy[v]]) hvy[v] = u;
				}
			}
		}
	}

	void bfs(int32 v, int32 t){
		queue<int32> q({v});
		while(q.size()){
			v = q.front(); q.pop();
			for(int32 i = v;i != -1;i=hvy[i]){
				typ[i] = t;
				vid[i] = pos++;
				inv[vid[i]] = i;
				head[i] = v;
				for(int32 u : G[i])
					if(u != par[i] && u != hvy[i]) q.push(u);
			}
		}
	}

	void for_each(int32 u, int32 v, const function<void(int32, int32)>& f){
		while(1){
			if(vid[u] > vid[v]) swap(u, v);
			f(max(vid[head[v]], vid[u]), vid[v]);
			if(head[u] != head[v]) v=par[head[v]];
			else break;
		}
	}

	void for_each_edge(int32 u, int32 v, const function<void(int32, int32)>& f){
		while(1){
			if(vid[u] > vid[v]) 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;
			}
		}
	}

	int32 lca(int32 u, int32 v){
		while(1){
			if(vid[u] > vid[v]) swap(u, v);
			if(head[u] != head[v]) v = par[head[v]];
			else return u;
		}
	}

	int32 distance(int32 u, int32 v){
		return dep[u]+dep[v]-2*dep[lca(u, v)];
	}

	int32 getvid(int32 v){
		return vid[v];
	}
};

template<typename T, typename E>
class LazySegTree{
private:
	using F = function<T(T, T)>;
	using G = function<T(T, E)>;
	using H = function<E(E, E)>;
	using P = function<E(E, int64)>;
	int32 n;
	vector<T> node;
	vector<E> lazy;
	F f;
	G g;
	H h;
	P p;
	T ti;
	E ei;
public:
	LazySegTree(){}
	LazySegTree(int32 _n, F f, G g, H h, T ti, E ei, P p = [](E a, int32 b){return a;}):f(f), g(g), h(h), p(p), ti(ti), ei(ei){
		init(_n);
	}

	LazySegTree(vector<T> v, F f, G g, H h, T ti, E ei, P p = [](E a, int32 b){return a;}):f(f), g(g), h(h), p(p), ti(ti), ei(ei){
		init(v.size());
		for(int32 i = 0;i < v.size();i++) node[i+n-1] = v[i];
		for(int32 i = n-2;i >= 0;i--) node[i] = merge(node[i*2+1], node[i*2+2]);
	}

	void init(int32 _n){
		n = 1;
		while(n < _n) n*=2;
		node.resize(2*n-1, ti);
		lazy.resize(2*n-1, ei);
	}

	inline T merge(T lhs, T rhs){
		if(lhs == ti) return rhs;
		else if(rhs == ti) return lhs;
		return f(lhs, rhs);
	}

	inline void eval(int32 k, int32 l, int32 r){
		if(lazy[k] == ei) return;
		node[k] = g(node[k], p(lazy[k], r-l));
		if(r-l > 1){
			lazy[k*2+1] = h(lazy[k*2+1], lazy[k]);
			lazy[k*2+2] = h(lazy[k*2+2], lazy[k]);
		}
		lazy[k] = ei;
	}

	T update(int32 a, int32 b, E x, int32 k=0, int32 l=0, int32 r=-1){
		if(r<0) r = n;
		eval(k, l, r);
		if(b <= l || r <= a) return node[k];
		if(a <= l && r <= b){
			lazy[k] = h(lazy[k], x);
			return g(node[k], p(lazy[k], r-l));
	}
		return node[k] = merge(update(a, b, x, k*2+1, l, (l+r)/2), update(a, b, x, k*2+2, (l+r)/2, r));
	}

	T query(int32 a, int32 b, int32 k=0, int32 l=0, int32 r=-1){
		if(r<0) r = n;
		eval(k, l, r);
		if(b <= l || r <= a) return ti;
		if(a <= l && r <= b) return node[k];
		return merge(query(a, b, k*2+1, l, (l+r)/2), query(a, b, k*2+2, (l+r)/2, r));
	}
};

int main(void){
	int32 N, Q;
	cin >> N;
	HLDecomposition hld(N);
	LazySegTree<int64, int64> lsg(N,
		[](int64 a, int64 b){return a+b;},
		[](int64 a, int64 b){return a+b;},
		[](int64 a, int64 b){return a+b;}, 0, 0);
	REP(i, N-1){
		int32 u, v;
		cin >> u >> v;
		u--; v--;
		hld.add_edge(u, v);
	}
	hld.build();
	cin >> Q;

	auto f = [&](int32 u, int32 v){
		lsg.update(u, v+1, 1);
	};

	REP(i, Q){
		int32 A, B;
		cin >> A >> B; A--; B--;
		hld.for_each(A, B, f);
	}
	int64 res = 0;
	REP(i, N){
		int64 x = lsg.query(i, i+1);
		res += x*(x+1)/2;
	}
	cout << res << endl;
}

yukicoder

結果

テストケース

ソースコード