結果

問題 No.1718 Random Squirrel
ユーザー cureskolcureskol
提出日時 2021-10-22 23:29:40
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 130 ms / 2,000 ms
コード長 2,920 bytes
コンパイル時間 2,791 ms
コンパイル使用メモリ 202,048 KB
実行使用メモリ 32,776 KB
最終ジャッジ日時 2023-10-24 15:38:33
合計ジャッジ時間 6,050 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 2 ms
4,348 KB
testcase_04 AC 2 ms
4,348 KB
testcase_05 AC 2 ms
4,348 KB
testcase_06 AC 2 ms
4,348 KB
testcase_07 AC 2 ms
4,348 KB
testcase_08 AC 2 ms
4,348 KB
testcase_09 AC 2 ms
4,348 KB
testcase_10 AC 2 ms
4,348 KB
testcase_11 AC 77 ms
12,976 KB
testcase_12 AC 12 ms
5,204 KB
testcase_13 AC 44 ms
9,016 KB
testcase_14 AC 79 ms
13,240 KB
testcase_15 AC 71 ms
11,656 KB
testcase_16 AC 30 ms
7,244 KB
testcase_17 AC 70 ms
12,448 KB
testcase_18 AC 100 ms
14,560 KB
testcase_19 AC 65 ms
11,392 KB
testcase_20 AC 21 ms
6,904 KB
testcase_21 AC 125 ms
16,936 KB
testcase_22 AC 130 ms
16,936 KB
testcase_23 AC 123 ms
16,936 KB
testcase_24 AC 115 ms
16,936 KB
testcase_25 AC 130 ms
16,936 KB
testcase_26 AC 48 ms
16,204 KB
testcase_27 AC 49 ms
16,244 KB
testcase_28 AC 33 ms
9,860 KB
testcase_29 AC 39 ms
9,016 KB
testcase_30 AC 68 ms
32,776 KB
testcase_31 AC 39 ms
9,016 KB
testcase_32 AC 39 ms
9,016 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In lambda function:
main.cpp:11:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   11 |   auto [a,b]=x;
      |        ^
main.cpp:12:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   12 |   auto [c,d]=y;
      |        ^
main.cpp: In member function 'void ReRooting<key_t, sum_t>::dfs2(int, int, sum_t)':
main.cpp:59:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   59 |       auto [a,b]=e.dp1;
      |            ^
main.cpp:66:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   66 |         auto [a,b]=e.dp2;
      |              ^
main.cpp:67:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   67 |         auto [c,d]=now;
      |              ^
main.cpp: In lambda function:
main.cpp:111:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  111 |     auto [a,b]=x;
      |          ^
main.cpp: In lambda function:
main.cpp:119:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  119 |     auto [a,b]=x;
      |          ^
main.cpp:120:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  120 |     auto [c,d]=y;
      |          ^
main.cpp: In function 'int main()':
main.cpp:133:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  133 |   for(auto &[x,y]:ans)cout<<x-y<<"\n";
      |             ^

ソースコード

diff # 

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=(n-1);i>=0;i--)
#define ALL(v) v.begin(),v.end()

using P=tuple<int,int>;
auto smerge=[](P x,P y)->P{
  auto [a,b]=x;
  auto [c,d]=y;
  return {a+c,max(b,d)};
};

template<typename key_t,typename sum_t=key_t>
struct ReRooting{
  struct Edge {
    int from,to;
    key_t cost;
    sum_t dp1,dp2;
    //dp1:部分木の内容
    //dp2:e=g[idx][i]の時、g[idx][0,i)のdp1の累積が入る
  };
  using F=function<sum_t(sum_t,sum_t)>;
  using G=function<sum_t(sum_t,Edge)>;
 
  vector<vector<Edge>> g;
  const F merge;
  const G score;
  const sum_t id;
  vector<sum_t> dp1,dp2;
  vector<int> ans;
  ReRooting(int n,const G &score,const F &merge,const sum_t &id=sum_t{})
    :g(n),merge(merge),score(score),id(id),dp1(n,id),dp2(n,id),ans(n){}
 
  void add_edge(int u,int v,const key_t &c){
    g[u].emplace_back(Edge{u,v,c,id,id});
    g[v].emplace_back(Edge{v,u,c,id,id});
  }
  void add_directed_edge(int u,int v,const key_t &c){
    g[u].emplace_back(Edge{u,v,c,id,id});
  }
 
  void dfs1(int idx,int pre){
    for(auto &e:g[idx])if(e.to!=pre){
      dfs1(e.to,idx);
      e.dp1=score(dp1[e.to],e);
      dp1[idx]=merge(dp1[idx],e.dp1);
    }
  }
 
  void dfs2(int idx,int pre,sum_t top){
    sum_t now=id;
    for(auto &e:g[idx]){
      e.dp2=now;
      if(e.to==pre)e.dp1=score(top,e);
      now=merge(now,e.dp1);
      auto [a,b]=e.dp1;
    }
    dp2[idx]=now;
    now=id;
    reverse(g[idx].begin(),g[idx].end());
    for(auto &e:g[idx]){
      if(e.to!=pre){
        auto [a,b]=e.dp2;
        auto [c,d]=now;
        dfs2(e.to,idx,smerge(e.dp2,now));
      }
      now=merge(now,e.dp1);
    }
  }
 
  vector<sum_t> build(){
    dfs1(0,-1);
    dfs2(0,-1,id);
    return dp2;
  }
};
const int INF=1e9+7;


int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n,k;cin>>n>>k;
  if(k==1){
    vector<vector<int>> g(n);
    REP(_,n-1){
      int u,v;cin>>u>>v;u--;v--;
      g[u].push_back(v);
      g[v].push_back(u);
    }
    int r;cin>>r;r--;
    vector<int> ans(n,-1);
    queue<int> que;
    que.push(r);
    ans[r]=0;
    while(que.size()){
      int p=que.front();que.pop();
      for(int q:g[p])if(ans[q]<0){
        ans[q]=ans[p]+1;
        que.push(q);
      }
    }
    REP(i,n)cout<<ans[i]<<"\n";
    return 0;
  }
  vector<bool> v(n,false);
  auto score=[&](P x,auto e)->P{
    auto [a,b]=x;
    if(a==0&&b==0){
      if(v[e.to])return {2,1};
      return {0,INF};
    }
    return {a+2,a+1-b};
  };
  auto merge=[&](auto x,auto y)->P{
    auto [a,b]=x;
    auto [c,d]=y;
    return {a+c,max(b,c-d)};
  };
  ReRooting<P> g(n,score,merge,{0,0});
  REP(_,n-1){
    int u,v;cin>>u>>v;u--;v--;
    g.add_edge(u,v,{0,INF});
  }
  REP(_,k){
    int a;cin>>a;a--;
    v[a]=true;
  }
  auto ans=g.build();
  for(auto &[x,y]:ans)cout<<x-y<<"\n";
}
0