結果
問題 | No.386 貪欲な領主 |
ユーザー | ei1333333 |
提出日時 | 2016-07-01 23:59:32 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 164 ms / 2,000 ms |
コード長 | 5,117 bytes |
コンパイル時間 | 1,892 ms |
コンパイル使用メモリ | 180,316 KB |
実行使用メモリ | 21,320 KB |
最終ジャッジ日時 | 2024-10-12 19:15:16 |
合計ジャッジ時間 | 3,399 ms |
ジャッジサーバーID (参考情報) |
judge2 / 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 | 115 ms
12,160 KB |
testcase_05 | AC | 164 ms
21,320 KB |
testcase_06 | AC | 154 ms
17,896 KB |
testcase_07 | AC | 3 ms
5,248 KB |
testcase_08 | AC | 20 ms
5,248 KB |
testcase_09 | AC | 4 ms
5,248 KB |
testcase_10 | AC | 2 ms
5,248 KB |
testcase_11 | AC | 2 ms
5,248 KB |
testcase_12 | AC | 2 ms
5,248 KB |
testcase_13 | AC | 6 ms
5,248 KB |
testcase_14 | AC | 163 ms
17,916 KB |
testcase_15 | AC | 96 ms
12,032 KB |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:173:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 173 | scanf("%d", &N); | ~~~~~^~~~~~~~~~ main.cpp:177:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 177 | scanf("%d %d", &A, &B); | ~~~~~^~~~~~~~~~~~~~~~~ main.cpp:187:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 187 | scanf("%d", &U[i]); | ~~~~~^~~~~~~~~~~~~ main.cpp:189:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 189 | scanf("%d", &M); | ~~~~~^~~~~~~~~~ main.cpp:193:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 193 | scanf("%d %d %d", &A, &B, &C); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include<bits/stdc++.h> using namespace std; vector< vector< int > > graph; struct BinaryIndexedTree { vector< int > data; BinaryIndexedTree(int sz) { data.assign(++sz, 0); } int sum(int k) { int ret = 0; for(++k; k > 0; k -= k & -k) ret += data[k]; return(ret); } void add(int k, int x) { for(++k; k < data.size(); k += k & -k) data[k] += x; } }; struct CentroidPathDecomposition { struct Centroid { int ParIndex, ParDepth, Deep; vector< int > node; inline int size() { return(node.size()); } inline int &operator[](int k) { return(node[k]); } inline pair< int, int > Up() { return(make_pair(ParIndex, ParDepth)); } Centroid(int x, int y, int z):ParIndex(x), ParDepth(y), Deep(z){}; }; vector< int > SubTreeSize, NextPath; vector< int > TreeIndex, TreeDepth; vector< Centroid > Centroids; void BuildSubTreeSize() { stack< pair< int, int > > s; s.push({0, -1}); while(!s.empty()) { auto p = s.top(); s.pop(); if(~SubTreeSize[p.first]) { NextPath[p.first] = -1; for(auto& to : graph[p.first]) { if(p.second == to) continue; SubTreeSize[p.first] += SubTreeSize[to]; if(NextPath[p.first] == -1 || SubTreeSize[NextPath[p.first]] < SubTreeSize[to]) { NextPath[p.first] = to; } } } else { s.push(p); SubTreeSize[p.first] = 1; for(auto& to : graph[p.first]) { if(p.second != to) s.push({to, p.first}); } } } } void BuildPath() { stack< pair< int, int > > s; Centroids.push_back((Centroid){-1, -1, 0}); s.push({0, -1}); TreeIndex[0] = 0; while(!s.empty()) { auto p = s.top(); s.pop(); TreeDepth[p.first] = Centroids[TreeIndex[p.first]].size(); for(auto& to : graph[p.first]) { if(p.second != to) { if(to == NextPath[p.first]) { // Centroid-Path TreeIndex[to] = TreeIndex[p.first]; } else { // Not Centroid-Path TreeIndex[to] = Centroids.size(); Centroids.emplace_back(TreeIndex[p.first], TreeDepth[p.first], Centroids[TreeIndex[p.first]].Deep + 1); } s.push({to, p.first}); } } Centroids[TreeIndex[p.first]].node.push_back(p.first); } } void AddEdge(int x, int y) { graph[x].push_back(y); graph[y].push_back(x); } void Build() { BuildSubTreeSize(); BuildPath(); } inline int size() { return(Centroids.size()); } inline pair< int, int > Information(int idx) { return(make_pair(TreeIndex[idx], TreeDepth[idx])); } inline Centroid &operator[](int k) { return(Centroids[k]); } inline int LCA(int a, int b) { int TreeIdxA, TreeDepthA, TreeIdxB, TreeDepthB; tie(TreeIdxA, TreeDepthA) = Information(a); tie(TreeIdxB, TreeDepthB) = Information(b); while(TreeIdxA != TreeIdxB) { if(Centroids[TreeIdxA].Deep > Centroids[TreeIdxB].Deep) { tie(TreeIdxA, TreeDepthA) = Centroids[TreeIdxA].Up(); } else { tie(TreeIdxB, TreeDepthB) = Centroids[TreeIdxB].Up(); } } if(TreeDepthA > TreeDepthB) swap(TreeDepthA, TreeDepthB); return(Centroids[TreeIdxA][TreeDepthA]); } CentroidPathDecomposition(int SZ) { graph.resize(SZ); SubTreeSize.assign(SZ, -1); NextPath.resize(SZ); TreeIndex.resize(SZ); TreeDepth.resize(SZ); } inline void AddPath(int A, int B, int C, vector< BinaryIndexedTree >& bits); }; inline void CentroidPathDecomposition::AddPath(int A, int B, int C, vector< BinaryIndexedTree >& bits) { int TreeIdxA, TreeDepthA, TreeIdxB, TreeDepthB; tie(TreeIdxA, TreeDepthA) = Information(A); tie(TreeIdxB, TreeDepthB) = Information(B); while(TreeIdxA != TreeIdxB) { if(Centroids[TreeIdxA].Deep > Centroids[TreeIdxB].Deep) { bits[TreeIdxA].add(0, C); bits[TreeIdxA].add(TreeDepthA + 1, -C); tie(TreeIdxA, TreeDepthA) = Centroids[TreeIdxA].Up(); } else { bits[TreeIdxB].add(0, C); bits[TreeIdxB].add(TreeDepthB + 1, -C); tie(TreeIdxB, TreeDepthB) = Centroids[TreeIdxB].Up(); } } if(TreeDepthA > TreeDepthB) swap(TreeDepthA, TreeDepthB); bits[TreeIdxA].add(TreeDepthA, C); bits[TreeIdxA].add(TreeDepthB + 1, -C); } int main() { int N, M, U[100000]; scanf("%d", &N); CentroidPathDecomposition tree(N); for(int i = 0; i < N - 1; i++) { int A, B; scanf("%d %d", &A, &B); tree.AddEdge(A, B); } tree.Build(); vector< BinaryIndexedTree > bits; for(int i = 0; i < tree.size(); i++) { bits.push_back(BinaryIndexedTree(tree[i].size() + 1)); } for(int i = 0; i < N; i++) { scanf("%d", &U[i]); } scanf("%d", &M); while(M--) { int A, B, C; scanf("%d %d %d", &A, &B, &C); tree.AddPath(A, B, C, bits); } long long ret = 0; for(int i = 0; i < N; i++) { int idx, depth; tie(idx, depth) = tree.Information(i); ret += 1LL * bits[idx].sum(depth) * U[i]; } printf("%lld\n", ret); }