#741632 (C++17) No.196 典型DP (1)

提出ソース

結果

問題	No.196 典型DP (1)
ユーザー	eQe
提出日時	2022-02-25 11:28:12
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	228 ms / 2,000 ms
コード長	4,329 bytes
コンパイル時間	5,001 ms
コンパイル使用メモリ	280,148 KB
実行使用メモリ	113,792 KB
最終ジャッジ日時	2024-07-03 04:15:39
合計ジャッジ時間	10,080 ms
ジャッジサーバーID （参考情報）	judge2 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	2 ms 5,376 KB
testcase_08	AC	2 ms 5,376 KB
testcase_09	AC	2 ms 5,376 KB
testcase_10	AC	2 ms 5,376 KB
testcase_11	AC	2 ms 5,376 KB
testcase_12	AC	2 ms 5,376 KB
testcase_13	AC	2 ms 5,376 KB
testcase_14	AC	2 ms 5,376 KB
testcase_15	AC	4 ms 5,376 KB
testcase_16	AC	7 ms 5,376 KB
testcase_17	AC	11 ms 5,376 KB
testcase_18	AC	19 ms 5,376 KB
testcase_19	AC	23 ms 5,504 KB
testcase_20	AC	30 ms 5,376 KB
testcase_21	AC	31 ms 5,376 KB
testcase_22	AC	30 ms 5,504 KB
testcase_23	AC	110 ms 43,904 KB
testcase_24	AC	85 ms 31,104 KB
testcase_25	AC	80 ms 27,648 KB
testcase_26	AC	227 ms 113,792 KB
testcase_27	AC	228 ms 113,664 KB
testcase_28	AC	227 ms 113,792 KB
testcase_29	AC	228 ms 113,792 KB
testcase_30	AC	227 ms 113,664 KB
testcase_31	AC	191 ms 5,376 KB
testcase_32	AC	191 ms 5,376 KB
testcase_33	AC	193 ms 5,376 KB
testcase_34	AC	190 ms 5,376 KB
testcase_35	AC	190 ms 5,376 KB
testcase_36	AC	175 ms 5,376 KB
testcase_37	AC	35 ms 5,376 KB
testcase_38	AC	175 ms 5,376 KB
testcase_39	AC	142 ms 5,376 KB
testcase_40	AC	186 ms 5,376 KB
testcase_41	AC	2 ms 5,376 KB
testcase_42	AC	2 ms 5,376 KB
testcase_43	AC	2 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <atcoder/all>
using namespace atcoder;
#include <bits/stdc++.h>
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define bitcnt(S) __builtin_popcountll(S)
using namespace std;
using ll=long long;
using ld=long double;
using pll=pair<ll,ll>;
template<class T>using ascending_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template<class T>using descending_priority_queue = priority_queue<T>;
template<class T>bool chmax(T &a, const T &b) {if(a<b) {a=b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if(b<a) {a=b; return 1;} return 0;}
istream& operator >> (istream& is, modint1000000007& x) { unsigned int t; is >> t; x=t; return is; }
istream& operator >> (istream& is, modint998244353& x) { unsigned int t; is >> t; x=t; return is; }
istream& operator >> (istream& is, modint& x) { unsigned int t; is >> t; x=t; return is; }
ostream& operator << (ostream& os, const modint1000000007& x) { os << x.val(); return os; }
ostream& operator << (ostream& os, const modint998244353& x) { os << x.val(); return os; }
ostream& operator << (ostream& os, const modint& x) { os << x.val(); return os; }
template<class T1, class T2>istream& operator >> (istream& is, pair<T1,T2>& p) { is >> p.first >> p.second; return is; }
template<class T1, class T2>ostream& operator << (ostream& os, const pair<T1,T2>& p) { os << p.first << " " << p.second; return os;}
template<class T>istream& operator >> (istream& is, vector<T>& v) { for(T& x:v) is >> x; return is; }
template<class T>ostream& operator << (ostream& os, const vector<T>& v) {for(int i=0;i<(int)v.size();i++) {os << v[i] << (i+1 == v.size() ? "":" ");} return os;}
template<class... A> void pt()      { std::cout << "\n"; }
template<class... A> void pt_rest() { std::cout << "\n"; }
template<class T, class... A> void pt_rest(const T& first, const A&... rest) { std::cout << " " << first; pt_rest(rest...); }
template<class T, class... A> void pt(const T& first, const A&... rest)      { std::cout << first; pt_rest(rest...); }
template<typename V, typename H> void resize(vector<V>& vec, const H head){ vec.resize(head); }
template<typename V, typename H, typename ... T> void resize(vector<V>& vec, const H& head, const T ... tail){ vec.resize(head); for(auto& v: vec) resize(v, tail...); }
template<typename V, typename T> void fill(V& x, const T& val){ x = val; }
template<typename V, typename T> void fill(vector<V>& vec, const T& val){ for(auto& v: vec) fill(v, val); }
template<typename H> void vin(istream& is, const int idx, vector<H>& head){ is >> head[idx]; }
template<typename H, typename ... T> void vin(istream& is, const int idx, vector<H>& head, T& ... tail){ vin(is >> head[idx], idx, tail...); }
template<typename H, typename ... T> void vin(istream& is, vector<H>& head, T& ... tail){ for(int i=0; i<(int)head.size(); i++) vin(is, i, head, tail...); }
template<typename H, typename ... T> void vin(vector<H>& head, T& ... tail){ vin(cin, head, tail...); }
map<ll,ll>divisor(ll n){map<ll,ll>res;for(ll i=1;i*i<=n;i++)if(n%i==0){res[i]++;res[n/i]++;}return res;}
map<ll,ll>factrization(ll n){map<ll,ll>res;for(ll i=2;i*i<=n;i++)while(n%i==0){res[i]++;n/=i;}if(n>1)res[n]++;return res;}
static const ll inf=1e18+7;
static const ld pi=acos(-1);
static const ld eps=1e-10;
using v1=vector<ll>;
using v2=vector<v1>;
using v3=vector<v2>;
using v4=vector<v3>;
using S=ll;
S op(S a,S b){return a+b;}
S e(){return 0;}

int main(void){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  
  ll N,K;cin>>N>>K;
  v2 g(N);
  for(ll i=0;i<N-1;i++){
    ll a,b;cin>>a>>b;
    g[a].emplace_back(b);
    g[b].emplace_back(a);
  }
  
  using mint=modint1000000007;
  vector<vector<vector<mint>>>dp(N);
  function<void(ll,ll)>f=[&](ll u,ll p){
    resize(dp[u],2,2);
    dp[u][0][0]=1;
    dp[u][1][1]=1;
    
    for(auto v:g[u])if(v!=p){
      f(v,u);
      
      ll n=dp[u].size();
      ll m=dp[v].size();
      vector<vector<mint>>nxt;resize(nxt,n+m-1,2);
      
      for(ll j=0;j<n;j++){
        for(ll k=0;k<2;k++){
          for(ll p=0;p<m;p++){
            for(ll q=k;q<2;q++){
              ll nj=j+p;
              ll nk=k&q;
              nxt[nj][nk]+=dp[u][j][k]*dp[v][p][q];
            }
          }
        }
      }
      swap(dp[u],nxt);
    }
  };
  f(0,-1);
  pt(dp[0][K][0]+dp[0][K][1]);
}

yukicoder

結果

テストケース

ソースコード