#505717 (C++14) No.1124 Earthquake Safety

提出ソース

結果

問題	No.1124 Earthquake Safety
ユーザー	QCFium
提出日時	2020-07-03 14:19:03
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	281 ms / 3,000 ms
コード長	1,657 bytes
コンパイル時間	1,934 ms
コンパイル使用メモリ	173,024 KB
実行使用メモリ	67,840 KB
最終ジャッジ日時	2024-09-16 17:08:52
合計ジャッジ時間	13,092 ms
ジャッジサーバーID （参考情報）	judge3 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	3 ms 5,376 KB
testcase_07	AC	7 ms 5,376 KB
testcase_08	AC	52 ms 9,344 KB
testcase_09	AC	210 ms 21,248 KB
testcase_10	AC	169 ms 67,840 KB
testcase_11	AC	2 ms 5,376 KB
testcase_12	AC	2 ms 5,376 KB
testcase_13	AC	2 ms 5,376 KB
testcase_14	AC	226 ms 21,248 KB
testcase_15	AC	224 ms 21,248 KB
testcase_16	AC	206 ms 21,248 KB
testcase_17	AC	209 ms 21,248 KB
testcase_18	AC	216 ms 21,120 KB
testcase_19	AC	231 ms 21,248 KB
testcase_20	AC	209 ms 21,248 KB
testcase_21	AC	270 ms 21,248 KB
testcase_22	AC	219 ms 21,248 KB
testcase_23	AC	213 ms 21,120 KB
testcase_24	AC	224 ms 21,120 KB
testcase_25	AC	205 ms 21,248 KB
testcase_26	AC	211 ms 21,248 KB
testcase_27	AC	202 ms 23,808 KB
testcase_28	AC	213 ms 23,808 KB
testcase_29	AC	231 ms 32,128 KB
testcase_30	AC	239 ms 32,128 KB
testcase_31	AC	259 ms 49,792 KB
testcase_32	AC	248 ms 46,464 KB
testcase_33	AC	263 ms 45,056 KB
testcase_34	AC	281 ms 49,024 KB
testcase_35	AC	194 ms 20,864 KB
testcase_36	AC	180 ms 20,864 KB
testcase_37	AC	195 ms 22,144 KB
testcase_38	AC	192 ms 21,888 KB
testcase_39	AC	175 ms 21,632 KB
testcase_40	AC	213 ms 22,272 KB
testcase_41	AC	209 ms 21,888 KB
testcase_42	AC	209 ms 22,272 KB
testcase_43	AC	163 ms 22,656 KB
testcase_44	AC	197 ms 22,528 KB
testcase_45	AC	191 ms 22,144 KB
testcase_46	AC	175 ms 22,528 KB
testcase_47	AC	184 ms 22,272 KB
testcase_48	AC	165 ms 22,576 KB
testcase_49	AC	163 ms 25,032 KB
testcase_50	AC	2 ms 5,376 KB
testcase_51	AC	2 ms 5,376 KB
testcase_52	AC	2 ms 5,376 KB
testcase_53	AC	2 ms 5,376 KB
testcase_54	AC	2 ms 5,376 KB
testcase_55	AC	2 ms 5,376 KB
testcase_56	AC	1 ms 5,376 KB
testcase_57	AC	1 ms 5,376 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

#define MOD 1000000007
#define inv2 500000004

std::vector<std::vector<int> > hen;

std::vector<int> subtree_dsum;
void dfs0(int i, int prev) {
	subtree_dsum[i] = inv2;
	for (auto j : hen[i]) if (j != prev) {
		dfs0(j, i);
		subtree_dsum[i] = (subtree_dsum[i] + (int64_t) subtree_dsum[j] * inv2) % MOD;
	}
}

int res = 0;
void dfs1(int i, int prev, int prev_dsum) {
	std::vector<int> all;
	if (prev != -1) all.push_back(prev_dsum);
	for (auto j : hen[i]) if (j != prev) all.push_back(subtree_dsum[j]);
	
	int sum = std::accumulate(all.begin(), all.end(), 0LL) % MOD;
	int sum2 = std::accumulate(all.begin(), all.end(), 0, [] (int a, int b) { return (a + (int64_t) b * b) % MOD; });
	int sum3 = std::accumulate(all.begin(), all.end(), 0, [] (int a, int b) { return (a + (int64_t) b * b % MOD * b) % MOD; });
	
	res = (res
		 + (int64_t) sum * sum % MOD * sum - (int64_t) sum2 * sum * 3 + sum3 * 2 // choose 3 from different arms
		 + ((int64_t) sum * sum - sum2) * 3 // 1 self + 2 from different arms
		 + (int64_t) sum * 3 + 1) % MOD; // 2 self + 1, 3 self
	if (res < 0) res += MOD;
	
	for (auto j : hen[i]) if (j != prev) {
		int next = (int64_t) (sum - subtree_dsum[j] + 1) * inv2 % MOD;
		if (next < 0) next += MOD;
		dfs1(j, i, next);
	}
}

int main() {
	int n = ri();
	hen.resize(n);
	for (int i = 1; i < n; i++) {
		int a = ri() - 1;
		int b = ri() - 1;
		hen[a].push_back(b);
		hen[b].push_back(a);
	}
	subtree_dsum.resize(n);
	dfs0(0, -1);
	
	dfs1(0, -1, 0);
	for (int i = 1; i < n; i++) {
		res += res;
		if (res >= MOD) res -= MOD;
	}
	printf("%d\n", res);
	return 0;
}

yukicoder

結果

テストケース

ソースコード