結果
問題 | No.196 典型DP (1) |
ユーザー | DAyamaCTF |
提出日時 | 2018-09-24 20:38:07 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 33 ms / 2,000 ms |
コード長 | 1,415 bytes |
コンパイル時間 | 1,792 ms |
コンパイル使用メモリ | 162,768 KB |
実行使用メモリ | 82,284 KB |
最終ジャッジ日時 | 2023-10-24 12:55:11 |
合計ジャッジ時間 | 5,282 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,348 KB |
testcase_01 | AC | 1 ms
4,348 KB |
testcase_02 | AC | 1 ms
4,348 KB |
testcase_03 | AC | 1 ms
4,348 KB |
testcase_04 | AC | 1 ms
4,348 KB |
testcase_05 | AC | 1 ms
4,348 KB |
testcase_06 | AC | 1 ms
4,348 KB |
testcase_07 | AC | 1 ms
4,348 KB |
testcase_08 | AC | 1 ms
4,348 KB |
testcase_09 | AC | 1 ms
4,348 KB |
testcase_10 | AC | 1 ms
6,068 KB |
testcase_11 | AC | 2 ms
6,072 KB |
testcase_12 | AC | 2 ms
6,072 KB |
testcase_13 | AC | 2 ms
8,120 KB |
testcase_14 | AC | 2 ms
8,120 KB |
testcase_15 | AC | 5 ms
18,376 KB |
testcase_16 | AC | 8 ms
32,732 KB |
testcase_17 | AC | 12 ms
47,096 KB |
testcase_18 | AC | 17 ms
61,456 KB |
testcase_19 | AC | 19 ms
69,656 KB |
testcase_20 | AC | 23 ms
76,464 KB |
testcase_21 | AC | 24 ms
78,308 KB |
testcase_22 | AC | 23 ms
76,464 KB |
testcase_23 | AC | 25 ms
77,100 KB |
testcase_24 | AC | 26 ms
76,868 KB |
testcase_25 | AC | 24 ms
76,784 KB |
testcase_26 | AC | 27 ms
78,116 KB |
testcase_27 | AC | 26 ms
78,032 KB |
testcase_28 | AC | 26 ms
78,004 KB |
testcase_29 | AC | 27 ms
78,096 KB |
testcase_30 | AC | 27 ms
82,284 KB |
testcase_31 | AC | 32 ms
81,980 KB |
testcase_32 | AC | 32 ms
81,980 KB |
testcase_33 | AC | 33 ms
81,980 KB |
testcase_34 | AC | 32 ms
81,980 KB |
testcase_35 | AC | 32 ms
81,980 KB |
testcase_36 | AC | 31 ms
81,980 KB |
testcase_37 | AC | 25 ms
81,972 KB |
testcase_38 | AC | 32 ms
81,980 KB |
testcase_39 | AC | 30 ms
81,980 KB |
testcase_40 | AC | 32 ms
81,980 KB |
testcase_41 | AC | 2 ms
4,348 KB |
testcase_42 | AC | 1 ms
4,348 KB |
testcase_43 | AC | 1 ms
4,348 KB |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:60:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 60 | scanf("%lld%lld",&N,&K); | ~~~~~^~~~~~~~~~~~~~~~~~ main.cpp:63:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 63 | scanf("%d%d",&a,&b); | ~~~~~^~~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll> P; #define fi first #define se second #define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++) #define rep(i,n) repl(i,0,n) #define all(x) (x).begin(),(x).end() #define dbg(x) cout<<#x"="<<x<<endl #define mmax(x,y) (x>y?x:y) #define mmin(x,y) (x<y?x:y) #define maxch(x,y) x=mmax(x,y) #define minch(x,y) x=mmin(x,y) #define uni(x) x.erase(unique(all(x)),x.end()) #define exist(x,y) (find(all(x),y)!=x.end()) #define bcnt __builtin_popcountll #define INF 1e16 #define mod 1000000007 ll N,K; ll cnt[5001]; ll dp[5001][5001]; ll dp2[2][5001]; vector<int> g[5001]; void dfs(int v,int pre){ cnt[v]=1; for(int nv : g[v]){ if(nv==pre)continue; dfs(nv,v); cnt[v]+=cnt[nv]; } int crt=0,nxt=1; rep(j,cnt[v]+1)dp2[crt][j]=0; dp2[crt][0]=1; for(int nv : g[v]){ if(nv==pre)continue; rep(j,cnt[v]+1)dp2[nxt][j]=0; rep(j,cnt[v]+1){ if(dp2[crt][j]==0)break; rep(k,cnt[nv]+1){ if(j+k<cnt[v])(dp2[nxt][j+k]+=dp2[crt][j]*dp[nv][k]%mod)%=mod; else break; } } swap(crt,nxt); } rep(j,cnt[v]){ dp[v][j]=dp2[crt][j]; } dp[v][cnt[v]]=1; } int main(){ scanf("%lld%lld",&N,&K); rep(i,N-1){ int a,b; scanf("%d%d",&a,&b); g[a].push_back(b); g[b].push_back(a); } dfs(0,-1); cout<<dp[0][K]<<endl; return 0; }