제출 #256075

#제출 시각아이디문제언어결과실행 시간메모리
256075anubhavdharCat in a tree (BOI17_catinatree)C++14
0 / 100
1 ms384 KiB
#include<bits/stdc++.h> #define ll long long #define pb push_back #define mp make_pair #define pii pair<int, int> #define pll pair<ll, ll> #define ff first #define ss second #define vi vector<int> #define vl vector<ll> #define vii vector<pii> #define vll vector<pll> #define FOR(i,N) for(i=0;i<(N);++i) #define FORe(i,N) for(i=1;i<=(N);++i) #define FORr(i,a,b) for(i=(a);i<(b);++i) #define FORrev(i,N) for(i=(N);i>=0;--i) #define F0R(i,N) for(int i=0;i<(N);++i) #define F0Re(i,N) for(int i=1;i<=(N);++i) #define F0Rr(i,a,b) for(ll i=(a);i<(b);++i) #define F0Rrev(i,N) for(int i=(N);i>=0;--i) #define all(v) (v).begin(),(v).end() #define dbgLine cerr<<" LINE : "<<__LINE__<<"\n" #define ldd long double using namespace std; const int Alp = 26; const int __PRECISION = 9; const int inf = 1e9 + 8; const ldd PI = acos(-1); const ldd EPS = 1e-7; const ll MOD = 1e9 + 7; const ll MAXN = 1507;//2e5 + 5; const ll ROOTN = 320; const ll LOGN = 18; const ll INF = 1e18 + 1022; int N, D, dis[MAXN], cat_cnt, mxdep[MAXN], dp[MAXN][MAXN]; vi g[MAXN]; void dfs(int a, int par) { for(int b : g[a]) if(b != par) dfs(b, a), dp[a][0] += dp[b][D-1]; F0Re(i, D-1) { int x = min(i, D-i); int y = D-x, sm = 0, mx = -inf; for(int b : g[a]) if(b != par) sm += dp[b][y-1], mx = max(dp[b][x-1] - dp[b][y-1], mx); dp[a][i] = sm + mx; } F0R(i, D) cat_cnt = max(cat_cnt, dp[a][i]); } signed main() { /* ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); */ /* int test_case_number; cin>>test_case_number; while(test_case_number--) test_case(); */ cin>>N>>D; if(D >= N) { cout<<"1\n"; exit(0); } if(D == 1) { cout<<N<<'\n'; exit(0); } cat_cnt = 0; F0Re(i, N) dis[i] = inf, mxdep[i] = 0; F0Re(i, N) F0R(j, D) dp[i][j] = (j==0) ? 1 : 0; F0Re(i, N-1) { int j; cin>>j; g[i+1].pb(j+1); g[j+1].pb(i+1); } // F0Re(i, N) // sort(all(g[i]), cmp); dfs(1, -1); cout<<cat_cnt<<'\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...