結果

問題 No.1718 Random Squirrel
ユーザー cureskolcureskol
提出日時 2021-10-22 23:05:41
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,287 bytes
コンパイル時間 2,483 ms
コンパイル使用メモリ 195,436 KB
実行使用メモリ 33,920 KB
最終ジャッジ日時 2024-09-23 07:00:45
合計ジャッジ時間 5,527 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 WA -
testcase_10 AC 2 ms
6,944 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 AC 48 ms
15,852 KB
testcase_27 WA -
testcase_28 AC 48 ms
15,708 KB
testcase_29 AC 70 ms
33,920 KB
testcase_30 WA -
testcase_31 AC 71 ms
33,920 KB
testcase_32 AC 72 ms
33,792 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In lambda function:
main.cpp:78:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   78 |     auto [a,b]=x;
      |          ^
main.cpp: In lambda function:
main.cpp:86:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   86 |     auto [a,b]=x;
      |          ^
main.cpp:87:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   87 |     auto [c,d]=y;
      |          ^
main.cpp: In function 'int main()':
main.cpp:100:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  100 |   for(auto &[x,y]:ans)cout<<max(0,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()

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;
  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){}
 
  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);
    }
    dp2[idx]=now;
    now=id;
    reverse(g[idx].begin(),g[idx].end());
    for(auto &e:g[idx]){
      if(e.to!=pre)
        dfs2(e.to,idx,merge(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;

using P=tuple<int,int>;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n,k;cin>>n>>k;
  vector<bool> v(n,false);
  auto score=[&](P x,auto e)->P{
    auto [a,b]=x;
    if(a==0&&b==INF){
      if(v[e.to])return {2,1};
      return {0,INF};
    }
    return {a+2,min(INF,b+1)};
  };
  auto merge=[&](auto x,auto y)->P{
    auto [a,b]=x;
    auto [c,d]=y;
    return {a+c,min(b,d)};
  };
  ReRooting<P> g(n,score,merge,{0,INF});
  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<<max(0,x-y)<<"\n";
}
0