Submission #3834001
Source Code Expand
#include <iostream> #include <stdio.h> #include <fstream> #include <algorithm> #include <string> #include <map> #include <set> #include <queue> #include <stack> #include <vector> #include <limits.h> #include <math.h> #include <functional> #include <bitset> #include <iomanip> #include <cassert> #define repeat(i,n) for (long long i = 0; (i) < (n); ++ (i)) #define debug(x) cerr << #x << ": " << x << '\n' #define debugArray(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i] << '\n' #define debugArrayP(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i].first<< " " << x[i].second << '\n' using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> Pii; typedef vector<int> vint; typedef vector<ll> vll; const ll INF = INT_MAX; const ll MOD = 1e9+7; int N,K; vector<vint> G; ll dp[112345][2]; ll size[112345]; ll cnt[112345]; void dfs(int v,int par){ size[v]=1; for(int chi:G[v])if(chi!=par){ dfs(chi,v); size[v] += size[chi]; cnt[v] += size[chi]>=K; } for(int chi:G[v])if(chi!=par){ dp[v][0] = max(dp[v][0],dp[chi][0]); if(size[chi]>1)dp[v][0] = max(dp[v][0],dp[chi][1]+(N-size[chi]>=K)); if(size[chi]>1)dp[v][0] = max(dp[v][0],dp[chi][1]+dp[v][1]-(size[chi]>=K)+(N-size[v]>=K)); dp[v][0] = max(dp[v][0],cnt[chi]+dp[v][1]-(size[chi]>=K)+(N-size[v]>=K)); if(size[chi]>1)dp[v][1] = max(dp[v][1],dp[chi][1]+cnt[v]-(size[chi]>=K)); dp[v][1] = max(dp[v][1],cnt[chi]+cnt[v]-(size[chi]>=K)); } } int main(){ cin.tie(0); ios::sync_with_stdio(false); cin >>N>>K; G.resize(N); repeat(i,N-1){ int u,v;cin>>u>>v;u--;v--; G[u].push_back(v); G[v].push_back(u); } dfs(0,-1); cout << max(dp[0][0],dp[0][1]) << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Tree Separator |
User | hashiryo |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 1869 Byte |
Status | AC |
Exec Time | 44 ms |
Memory | 13952 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 100 / 100 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 00_sample_00, 00_sample_01, 00_sample_02, 00_sample_03, 00_sample_04, 00_sample_05, 10_small_0, 10_small_1, 10_small_2, 10_small_3, 10_small_4, 20_random_0, 20_random_1, 20_random_2, 20_random_3, 20_random_4, 30_small_k_0, 30_small_k_1, 30_small_k_2, 30_small_k_3, 30_small_k_4, 30_small_k_5, 30_small_k_6, 30_small_k_7, 30_small_k_8, 30_small_k_9, 90_star_0, 90_star_1, 91_path_0, 91_path_1, 92_star_like_0, 92_star_like_1, 92_star_like_2, 92_star_like_3, 92_star_like_4 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_00 | AC | 1 ms | 256 KB |
00_sample_01 | AC | 1 ms | 256 KB |
00_sample_02 | AC | 1 ms | 256 KB |
00_sample_03 | AC | 1 ms | 256 KB |
00_sample_04 | AC | 1 ms | 256 KB |
00_sample_05 | AC | 1 ms | 256 KB |
10_small_0 | AC | 1 ms | 256 KB |
10_small_1 | AC | 1 ms | 256 KB |
10_small_2 | AC | 1 ms | 256 KB |
10_small_3 | AC | 1 ms | 256 KB |
10_small_4 | AC | 1 ms | 256 KB |
20_random_0 | AC | 27 ms | 5760 KB |
20_random_1 | AC | 4 ms | 768 KB |
20_random_2 | AC | 43 ms | 8704 KB |
20_random_3 | AC | 13 ms | 2944 KB |
20_random_4 | AC | 5 ms | 1152 KB |
30_small_k_0 | AC | 22 ms | 4608 KB |
30_small_k_1 | AC | 24 ms | 5120 KB |
30_small_k_2 | AC | 9 ms | 2048 KB |
30_small_k_3 | AC | 32 ms | 6656 KB |
30_small_k_4 | AC | 40 ms | 8320 KB |
30_small_k_5 | AC | 6 ms | 1408 KB |
30_small_k_6 | AC | 23 ms | 4864 KB |
30_small_k_7 | AC | 12 ms | 2688 KB |
30_small_k_8 | AC | 11 ms | 2560 KB |
30_small_k_9 | AC | 24 ms | 5120 KB |
90_star_0 | AC | 30 ms | 6904 KB |
90_star_1 | AC | 30 ms | 6904 KB |
91_path_0 | AC | 44 ms | 13952 KB |
91_path_1 | AC | 41 ms | 13440 KB |
92_star_like_0 | AC | 36 ms | 9084 KB |
92_star_like_1 | AC | 35 ms | 9084 KB |
92_star_like_2 | AC | 37 ms | 9084 KB |
92_star_like_3 | AC | 37 ms | 9084 KB |
92_star_like_4 | AC | 37 ms | 9084 KB |