#34496 (C++11) No.235 めぐるはめぐる (5)

提出ソース

結果

問題	No.235 めぐるはめぐる (5)
ユーザー	Kmcode1
提出日時	2015-06-27 01:01:57
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	894 ms / 10,000 ms
コード長	5,577 bytes
コンパイル時間	1,320 ms
コンパイル使用メモリ	119,396 KB
実行使用メモリ	102,116 KB
最終ジャッジ日時	2024-07-07 19:48:40
合計ジャッジ時間	5,641 ms
ジャッジサーバーID （参考情報）	judge5 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	894 ms 91,128 KB
testcase_01	AC	582 ms 102,116 KB
testcase_02	AC	750 ms 93,744 KB

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

コンパイルメッセージ

main.cpp: In function ‘int main()’:
main.cpp:237:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  237 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
main.cpp:239:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  239 |                 scanf("%lld", &s[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~
main.cpp:242:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  242 |                 scanf("%lld", &c[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~
main.cpp:246:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  246 |                 scanf("%d%d", &a, &b);
      |                 ~~~~~^~~~~~~~~~~~~~~~
main.cpp:261:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  261 |         scanf("%d", &q);
      |         ~~~~~^~~~~~~~~~
main.cpp:264:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  264 |                 scanf("%d", &ty);
      |                 ~~~~~^~~~~~~~~~~
main.cpp:268:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  268 |                         scanf("%d%d%lld", &a, &b, &z);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:278:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  278 |                         scanf("%d%d", &a, &b);
      |                         ~~~~~^~~~~~~~~~~~~~~~

ソースコード

raw source code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cctype>
#include<cstdlib>
#include<algorithm>
#include<bitset>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<ctime>
#include<complex>
#include<functional>
#include<climits>
#include<cassert>
#include<iterator>
#include<unordered_map>
using namespace std;
#define MOD 1000000007
#define MAX 200002
class L{  //lazy segmenttree for HL decomposition
public:
	struct st{
		long long int lazy = 0;  //for ans
		long long int sum = 0;  //sum of c
		long long int ans = 0;  //ans sum
		int l = 0;
		int r = 0;
		long long int area = 0;
	};
	vector<st> seg;
	vector<long long int> C;
	vector<long long int> S;
	int N = 0;
	void update(int b){
		seg[b].ans += seg[b].sum*seg[b].lazy;
		seg[b].ans %= MOD;
		if (seg[b].l + 1 == seg[b].r){
			seg[b].lazy = 0;
			return;
		}
		seg[b * 2 + 1].lazy += seg[b].lazy;
		seg[b * 2 + 2].lazy += seg[b].lazy;
		seg[b * 2 + 1].lazy %= MOD;
		seg[b * 2 + 2].lazy %= MOD;
		seg[b].lazy = 0;
	}
	inline void init(int b, int l, int r){
		seg[b].l = l;
		seg[b].r = r;
		seg[b].area = r - l;
		if (l + 1 == r){
			seg[b].sum = C[l];
			seg[b].ans = S[l];
			return;
		}
		init(b * 2 + 1, l, (l + r) >> 1);
		init(b * 2 + 2, (l + r) >> 1, r);
		seg[b].sum = seg[b * 2 + 1].sum + seg[b * 2 + 2].sum;
		seg[b].sum %= MOD;
		seg[b].ans = seg[b * 2 + 1].ans + seg[b * 2 + 2].ans;
		seg[b].ans %= MOD;
	}
	inline void add1(int b, int l, int r, int ll, int rr, int x){
		update(b);
		if (ll <= l&&r <= rr){
			seg[b].lazy = x;
			update(b);
			return;
		}
		if (r <= ll || rr <= l){
			return;
		}
		add1(b * 2 + 1, l, (l + r) >> 1, ll, rr, x);
		add1(b * 2 + 2, (l + r) >> 1, r, ll, rr, x);
		seg[b].ans = seg[b * 2 + 1].ans + seg[b * 2 + 2].ans;
		seg[b].ans %= MOD;
	}
	inline long long int q(int b, int l, int r, int ll, int rr){
		update(b);
		if (r <= ll || rr <= l){
			return 0;
		}
		if (ll <= l&&r <= rr){
			return seg[b].ans;
		}
		long long int R = q(b * 2 + 1, l, (l + r) >> 1, ll, rr);
		long long int RR = q(b * 2 + 2, (l + r) >> 1, r, ll, rr);
		R += RR;
		R %= MOD;
		return R;
	}
	void set(int n){
		N = n;
		seg.assign(n * 4, st());
		init(0, 0, N);
	}
	long long int sum(int l, int r){
		return q(0, 0, N, l, r);
	}
	void add(int l, int r, long long int x){
		add1(0, 0, N, l, r, x);
	}
};
/*tree*/
int countt[MAX];
int dep[MAX];
bool use[MAX];  //visited
vector<int> v[MAX];  //graph
vector<int> g[MAX];  //tree
int n;

/*lca*/
#define MAX_LOG 21
int lcc[MAX_LOG][MAX];
void init(){
	for (int i = 0; i + 1 < MAX_LOG; i++){
		for (int j = 0; j < n; j++){
			if (lcc[i][j] == -1){
				lcc[i + 1][j] = -1;
				continue;
			}
			lcc[i + 1][j] = lcc[i][lcc[i][j]];
		}
	}
}
int lca(int a, int b){
	if (dep[a] < dep[b]){
		swap(a, b);
	}
	for (int i = 0; i < MAX_LOG; i++){
		if (((dep[a] - dep[b]) >> i) & 1){
			a = lcc[i][a];
		}
	}
	if (a == b){
		return a;
	}
	for (int i = MAX_LOG - 1; i >= 0; i--){
		if (lcc[i][a] != lcc[i][b]){
			a = lcc[i][a];
			b = lcc[i][b];
		}
	}
	return lcc[0][a];
}

/*HL*/
int belong[MAX];
int att[MAX];
vector<L> HL;
long long int s[MAX];
long long int c[MAX];
int pr[MAX];


inline void dfs(int b, int pre = -1, int h = 0){  //make tree
	dep[b] = h;
	lcc[0][b] = pre;
	use[b] = true;
	countt[b] = 1;
	for (int i = 0; i < v[b].size(); i++){
		if (use[v[b][i]] == false){
			dfs(v[b][i], b, h + 1);
			g[b].push_back(v[b][i]);
			countt[b] += countt[v[b][i]];
		}
	}
}

inline void dfs2(int a, int b, int cc){  //HL decomposition
	belong[a] = b;
	att[a] = cc;
	HL[b].S.push_back(s[a]);
	HL[b].C.push_back(c[a]);
	if (v[a].size() == 0){
		HL[b].set(cc + 1);
		return;
	}
	int maxt = 0;
	int ind = 0;
	for (int i = 0; i < v[a].size(); i++){
		if (maxt <= countt[v[a][i]]){
			maxt = countt[v[a][i]];
			ind = i;
		}
	}
	for (int i = 0; i < v[a].size(); i++){
		if (i == ind){
			dfs2(v[a][i], b, cc + 1);
		}
		else{
			pr[HL.size()] = a;
			HL.push_back(L());
			dfs2(v[a][i], HL.size() - 1, 0);
		}
	}
}


void paint(int a, int b, long long int z){  //type 0
	long long int r = 0;
	while (belong[b] != belong[a]){
		HL[belong[b]].add(0, att[b] + 1, z);
		b = pr[belong[b]];
	}
	HL[belong[b]].add(att[a], att[b] + 1, z);
}

long long int sum_up(int a, int b){  //type 1
	long long int r = 0;
	while (belong[b] != belong[a]){
		r += HL[belong[b]].sum(0, att[b] + 1);
		if (r >= MOD){
			r %= MOD;
		}
		b = pr[belong[b]];
	}
	r += HL[belong[b]].sum(att[a], att[b] + 1);
	if (r >= MOD){
		r %= MOD;
	}
	return r;
}


int main(){
	scanf("%d", &n);
	for (int i = 0; i < n; i++){
		scanf("%lld", &s[i]);
	}
	for (int i = 0; i < n; i++){
		scanf("%lld", &c[i]);
	}
	for (int i = 1; i < n; i++){
		int a, b;
		scanf("%d%d", &a, &b);
		a--;
		b--;
		v[a].emplace_back(b);
		v[b].emplace_back(a);
	}
	dfs(0);
	init();
	pr[0] = -1;
	HL.push_back(L());
	for (int i = 0; i < n; i++){
		v[i] = g[i];
	}
	dfs2(0, 0, 0);
	int q;
	scanf("%d", &q);
	while (q--){
		int ty;
		scanf("%d", &ty);
		if (ty == 0){
			int a, b;
			long long int z;
			scanf("%d%d%lld", &a, &b, &z);
			a--;
			b--;
			int lc = lca(a, b);
			paint(lc, b, z);
			paint(lc, a, z);
			paint(lc, lc, -z);
		}
		else{
			int a, b;
			scanf("%d%d", &a, &b);
			a--;
			b--;
			int lc = lca(a, b);
			long long int ans = sum_up(lc, a);
			ans += sum_up(lc, b);
			if (ans >= MOD){
				ans %= MOD;
			}
			ans += MOD - sum_up(lc, lc);
			ans %= MOD;
			while (ans < 0){
				ans += MOD;
			}
			printf("%lld\n", ans);
		}
	}
	return 0;
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード