#601577 (C++17) No.1333 Squared Sum

提出ソース

結果

問題	No.1333 Squared Sum
ユーザー	りあん
提出日時	2021-01-08 23:28:37
言語	C++17 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	512 ms / 2,000 ms
コード長	1,858 bytes
コンパイル時間	2,151 ms
コンパイル使用メモリ	204,716 KB
実行使用メモリ	50,272 KB
最終ジャッジ日時	2023-08-10 12:29:08
合計ジャッジ時間	15,488 ms
ジャッジサーバーID （参考情報）	judge15 / judge12

このコードへのチャレンジ（β）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	6 ms 15,244 KB
testcase_01	AC	6 ms 15,220 KB
testcase_02	AC	6 ms 15,112 KB
testcase_03	AC	394 ms 23,180 KB
testcase_04	AC	431 ms 23,204 KB
testcase_05	AC	358 ms 23,288 KB
testcase_06	AC	429 ms 23,176 KB
testcase_07	AC	452 ms 23,228 KB
testcase_08	AC	361 ms 23,156 KB
testcase_09	AC	387 ms 23,236 KB
testcase_10	AC	377 ms 23,224 KB
testcase_11	AC	388 ms 23,296 KB
testcase_12	AC	358 ms 23,184 KB
testcase_13	AC	362 ms 50,272 KB
testcase_14	AC	457 ms 36,484 KB
testcase_15	AC	512 ms 46,892 KB
testcase_16	AC	6 ms 15,072 KB
testcase_17	AC	6 ms 15,084 KB
testcase_18	AC	6 ms 15,068 KB
testcase_19	AC	6 ms 15,116 KB
testcase_20	AC	6 ms 15,188 KB
testcase_21	AC	6 ms 15,068 KB
testcase_22	AC	6 ms 15,120 KB
testcase_23	AC	6 ms 15,120 KB
testcase_24	AC	6 ms 15,124 KB
testcase_25	AC	6 ms 15,108 KB
testcase_26	AC	505 ms 49,528 KB
testcase_27	AC	479 ms 37,076 KB
testcase_28	AC	469 ms 49,236 KB
testcase_29	AC	368 ms 50,228 KB
testcase_30	AC	127 ms 18,468 KB
testcase_31	AC	71 ms 17,008 KB
testcase_32	AC	197 ms 19,988 KB
testcase_33	AC	145 ms 18,988 KB
testcase_34	AC	286 ms 21,612 KB
testcase_35	AC	204 ms 20,116 KB
testcase_36	AC	108 ms 18,020 KB
testcase_37	AC	115 ms 18,240 KB
testcase_38	AC	138 ms 18,640 KB
testcase_39	AC	269 ms 20,724 KB
testcase_40	AC	265 ms 26,352 KB
testcase_41	AC	263 ms 26,268 KB
testcase_42	AC	256 ms 26,328 KB
testcase_43	AC	240 ms 26,272 KB

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

ソースコード

raw source code

// https://atcoder.jp/contests/otemae2019/submissions/6651746

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;

int N;
vector<pair<int, int>> G[500000];

ll ans = 0;

int subnum[500000];
int calc_subnum(int v, int from) {
	int ret = 1;
	for (int i = 0; i < G[v].size(); i++){
		int to = G[v][i].second;
		if (to == from)continue;
		ret += calc_subnum(to, v);
	}
	return subnum[v] = ret;
}

//eを通るu-v pathの個数
void calc1(int v, int from, int l) {
	ans += (ll)subnum[v] * (N - subnum[v]) % mod * l % mod * l;
	ans %= mod;
	for (int i = 0; i < G[v].size(); i++) {
		int to = G[v][i].second;
		if (to == from)continue;
		calc1(to, v, G[v][i].first);
	}
}
//根とe'の間にe
ll calc2(int v, int from) {
	ll ret = 0;
	for (int i = 0; i < G[v].size(); i++) {
		int to = G[v][i].second;
		if (to == from)continue;
		ll next = calc2(to, v);
		ans += next * (N - subnum[to]) % mod * G[v][i].first; ans %= mod;
		ret += next; ret += subnum[to] * (ll)G[v][i].first; ret %= mod;
	}
	return ret;
}//eとe'がバラバラ
ll calc3(int v, int from) {
	ll ret = 0;
	vector<ll> x;
	for (int i = 0; i < G[v].size(); i++) {
		int to = G[v][i].second;
		if (to == from)continue;
		ll next = (calc3(to, v) + subnum[to] * (ll)G[v][i].first) % mod;
		x.push_back(next); ret += next; ret %= mod;
	}
	ll sum = 0;
	for (int i = 0; i < x.size(); i++) {
		sum += x[i];
	}
	sum %= mod;
	for (int i = 0; i < x.size(); i++) {
		ans += x[i] * (sum - x[i] + mod); ans %= mod;
	}
	return ret;
}
int main() {
	cin >> N;
	//入力
	for (int i = 0; i < N - 1; i++) {
		int A, B, C; cin >> A >> B >> C; A--; B--;
		G[A].push_back({C, B});
		G[B].push_back({C, A});
	}

	calc_subnum(0, -1);
	calc1(0, -1, 0);
	calc2(0, -1);
	//eとe'の上下を入れ替えてもう一度
	calc2(0, -1);
	calc3(0, -1);

	cout << ans << endl;
	return 0;
}

yukicoder

結果

テストケース

ソースコード