結果

問題 No.386 貪欲な領主
ユーザー kyuridenamida
提出日時 2016-07-01 23:13:03
言語 C++11
(gcc 13.3.0)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 5,069 bytes
コンパイル時間 2,345 ms
コンパイル使用メモリ 192,428 KB
実行使用メモリ 35,916 KB
最終ジャッジ日時 2024-10-12 19:05:43
合計ジャッジ時間 10,044 ms
ジャッジサーバーID
(参考情報)
judge5 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other RE * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In member function ‘long long int Tree::gen_lca()’:
main.cpp:100:9: warning: no return statement in function returning non-void [-Wreturn-type]
  100 |         }
      |         ^
main.cpp: In member function ‘long long int Tree::dfs(const std::vector<std::vector<long long int> >&)’:
main.cpp:118:9: warning: no return statement in function returning non-void [-Wreturn-type]
  118 |         }
      |         ^
main.cpp: In member function ‘bool Tree::verify()’:
main.cpp:74:9: warning: control reaches end of non-void function [-Wreturn-type]
   74 |         }
      |         ^

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0 ; i < (n) ; i++)
#define int long long
// int64bit int!!!
template<class T>
struct SegmentTree{
int n_;
vector<T> seg;
// [1,N]
SegmentTree(int N){
n_ = 1;
while(n_ < N ) n_ *= 2;
seg.resize(2*n_,0); //
}
void add(int i,int j,int v){
i += n_-1;
seg[i] = v;
i /= 2;
while(i){
seg[i] = seg[i*2] + seg[i*2+1]; //
i /= 2;
}
}
T get(int l,int r,int k,int a,int b){
if( b < l || r < a ) return 0; //
if( l <= a && b <= r ){
return seg[k];
}
int m = (a+b)/2;
return get(l,r,k*2,a,m) + get(l,r,k*2+1,m+1,b); //
}
inline T get(int l,int r){
return get(l,r,1,1,n_);
}
};
class Tree{
public:
//[0,n)
int n,logn,root;
vector<vector<int>> child;
vector<vector<int>> parent;
vector<pair<int,int>> edges;
vector<int> depth;
Tree(int n_,vector<pair<int,int>> es,int root) : root(root){
edges = es;
n = n_;
logn = 0;
while(n_){
++logn;
n_ /= 2;
}
parent.resize(logn,vector<int>(n,-1));
depth.resize(n,-1);
child.resize(n);
vector<vector<int>> g(n);
for( auto e : es ){
g[e.first].push_back(e.second);
g[e.second].push_back(e.first);
}
dfs(g);
gen_lca();
verify();
}
bool verify(){
for(int i = 0 ; i < n ; i++)
assert( depth[i] != -1 );
}
int lca(int x,int y){
if( depth[x] < depth[y] )swap(x,y);
int d = depth[x] - depth[y];
for(int i = 0 ; i < logn ; i++)
if( d >> i & 1 ) x = parent[i][x];
if( x == y ) return x;
for(int i = logn-1 ; i >= 0 ; i--){
if( parent[i][x] != parent[i][y] ){
x = parent[i][x];
y = parent[i][y];
}
}
return parent[0][x];
}
int distance(int x,int y){
return depth[x] + depth[y] - 2 * depth[lca(x,y)];
}
private:
int gen_lca(){
for(int i = 1 ; i < logn ; i++){
for(int j = 0 ; j < n ; j++)
if( parent[i-1][j] != -1 )
parent[i][j] = parent[i-1][parent[i-1][j]];
}
}
int dfs(const vector<vector<int>> &g){
stack< array<int,3> > S;
S.push(array<int,3>{root,-1,0});
while( S.size() ){
int x = S.top()[0];
int p = S.top()[1];
int d = S.top()[2];
S.pop();
parent[0][x] = p;
depth[x] = d;
for( auto e : g[x] ){
if( e != p ){
S.push(array<int,3>{e,x,d+1});
child[x].push_back(e);
}
}
}
}
};
template<class SegmentTree> class HeavyLightDecomp{
public:
Tree tr;
vector< pair<int,int> > where; // (id,pos)
vector< vector<int> > pathSeq;
vector<SegmentTree> seg;
HeavyLightDecomp(const Tree &tr) : tr(tr){
// init
where.resize(tr.n,{-1,-1});
vector<int> subtree(tr.n);
vector<pair<int,int>> sortedIdx;
for(int i = 0 ; i < tr.n ; i++)
sortedIdx.push_back({tr.depth[i],i});
sort(sortedIdx.begin(),sortedIdx.end());
// calc sizes of each subtree
for(int I = tr.n-1 ; I >= 0 ; I--){
int i = sortedIdx[I].second;
subtree[i] = 1;
for( auto e : tr.child[i] ) subtree[i] += subtree[e];
}
// do heavyLightDecomp Part1
for(int I = 0 ; I < tr.n ; I++){
int i = sortedIdx[I].second;
if( where[i].first == -1 ){
where[i].first = pathSeq.size();
pathSeq.push_back(vector<int>());
}
where[i].second = pathSeq[where[i].first].size();
pathSeq[where[i].first].push_back(i);
for( auto e : tr.child[i] ){
if( 2*subtree[e] > subtree[i] ){
where[e].first = where[i].first;
}
}
}
// Set segtrees to each heavy-path.
for(int i = 0 ; i < pathSeq.size() ; i++){
int n_ = 1;
while( n_ < pathSeq[i].size() ) n_ *= 2;
seg.push_back(SegmentTree(n_));
}
}
//
void addToVertex(int a,int b,int x){
int p = tr.lca(a,b);
add(a,p,x,1); //
add(b,p,x,0); //
}
int getToVertex(int a,int b){
int p = tr.lca(a,b);
return get(a,p,1) + get(b,p,0); //
}
private:
inline void add(int c,int p,int x,int isEdgeQuery){
int id1 = where[c].first;
int id2 = where[p].first;
int l = where[p].second + 1;
int r = where[c].second + 1;
if( id1 == id2 ){
if( l+isEdgeQuery <= r ) seg[id1].add(l+isEdgeQuery,r,x); //
}else{
seg[id1].add(1,r,x); //
add(tr.parent[0][pathSeq[id1][0]],p,x,isEdgeQuery);
}
}
inline int get(int c,int p,int isEdgeQuery){
int id1 = where[c].first;
int id2 = where[p].first;
int l = where[p].second + 1;
int r = where[c].second + 1;
int ans = 0;
if( id1 == id2 ){
ans += seg[id1].get(l+isEdgeQuery,r); //
}else{
ans += seg[id1].get(1,r); //
ans += get(tr.parent[0][pathSeq[id1][0]],p,isEdgeQuery);
}
return ans;
}
};
signed main(){
int n;
cin >> n;
vector< pair<int,int> > es;
for(int i = 0 ; i < n - 1 ; i++){
int a,b;
cin >> a >> b;
es.push_back({a,b});
}
Tree tree(n,es,0);
HeavyLightDecomp<SegmentTree<int>> hl(tree);
for(int i = 0 ; i < n ; i++){
int w;
cin >> w;
hl.addToVertex(i,i,w);
}
int q;
cin >> q;
int ans = 0;
for(int i = 0 ; i < q ; i++){
int a,b,c;
cin >> a >> b >> c;
ans += c * hl.getToVertex(a,b);
}
cout << ans << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0