結果
問題 | No.386 貪欲な領主 |
ユーザー |
|
提出日時 | 2016-07-01 22:53:07 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 233 ms / 2,000 ms |
コード長 | 1,777 bytes |
コンパイル時間 | 1,550 ms |
コンパイル使用メモリ | 166,768 KB |
実行使用メモリ | 29,188 KB |
最終ジャッジ日時 | 2024-10-12 03:50:41 |
合計ジャッジ時間 | 3,547 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:72:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 72 | scanf("%d %d", &u, &v); | ~~~~~^~~~~~~~~~~~~~~~~ main.cpp:79:42: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 79 | for (int i = 0; i < n; i++) scanf("%lld", &cost[i]); | ~~~~~^~~~~~~~~~~~~~~~~~ main.cpp:87:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 87 | scanf("%d %d %d", &a, &b, &c); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h>using namespace std;class LCA {public:LCA(int n) : g(n), parent(21, vector<int>(n, -1)), depth(n) {}void add(int u, int v) {g[u].push_back(v);g[v].push_back(u);}void build() {dfs(0, -1);for (int i = 0; i < 20; i++) {for (int j = 0; j < g.size(); j++) {if (parent[i][j] != -1) {parent[i + 1][j] = parent[i][parent[i][j]];}}}}int query(int u, int v) {if (depth[u] < depth[v]) swap(u, v);for (int i = 20; i >= 0; i--) {if (depth[u] - depth[v] >= 1 << i) {u = parent[i][u];}}if (u == v) return u;for (int i = 20; i >= 0; i--) {if (parent[i][u] != parent[i][v]) {u = parent[i][u];v = parent[i][v];}}return parent[0][u];}private:vector<vector<int>> g, parent;vector<int> depth;void dfs(int curr, int prev) {parent[0][curr] = prev;for (int next : g[curr]) if (next != prev) {depth[next] = depth[curr] + 1;dfs(next, curr);}}};vector<int> g[101010];long long cost[101010];long long imos[101010];void dfs(int curr, int prev) {for (int next : g[curr]) if (next != prev) {dfs(next, curr);}if (prev != -1) imos[prev] += imos[curr];}int main() {int n;cin >> n;LCA lca(n);for (int i = 0; i < n - 1; i++) {int u, v;scanf("%d %d", &u, &v);g[u].push_back(v);g[v].push_back(u);lca.add(u, v);}lca.build();for (int i = 0; i < n; i++) scanf("%lld", &cost[i]);long long ans = 0;int m;cin >> m;for (int i = 0; i < m; i++) {int a, b, c;scanf("%d %d %d", &a, &b, &c);int l = lca.query(a, b);ans += c * cost[l];imos[a] += c;imos[b] += c;imos[l] -= 2 * c;}dfs(0, -1);for (int i = 0; i < n; i++) {ans += cost[i] * imos[i];}cout << ans << endl;}