Submission #2474720
Source Code Expand
#include <bits/stdc++.h> using namespace std; const int maxn = 100010; int n,k,num[maxn],need[maxn]; int dp[maxn][2][3],m1[maxn],m2[maxn]; vector<int> tree[maxn]; int dfs1(int v,int u){ num[v] = 1;need[v] = 0; for(int i=0;i<tree[v].size();i++){ int t = tree[v][i]; if(t==u) continue; num[v] += dfs1(t,v); if(num[t]>=k) need[v]++; } return num[v]; } int dfs(int v,int u){ dp[v][1][0] = 0; if(num[v]>=k) dp[v][1][0] = 1; for(int i=0;i<tree[v].size();i++){ int t = tree[v][i]; int f = num[t]>=k?1:0; if(t==u) continue; if(dp[t][1][0]>=0) dp[v][1][0] = max(dp[v][1][0],need[v]+dp[t][1][0]-f); else dp[v][1][0] = max(dp[v][1][0],need[v]+dfs(t,v)-f); } return dp[v][1][0]; } int dfs2(int v,int u){ int ans = 0; if(n-num[v]>=k&&num[v]>=2) ans = 1; int f = (n - num[v])>=k?1:0; for(int i=0;i<tree[v].size();i++){ int t = tree[v][i]; int g = num[t]>=k?1:0; if(t==u) continue; ans = max(ans,dfs2(t,v)); int add = (m1[v]==(dp[v][1][0]-g))?m2[v]:m1[v]; ans = max(ans,dp[t][1][1]+need[v]-g+f+add); } return ans; } void dfs3(int v,int u){ dp[v][1][1] = 0; for(int i=0;i<tree[v].size();i++){ int t = tree[v][i]; if(t==u) continue; int g = num[t]>=k?1:0; dp[v][1][1] = max(dp[v][1][1],need[v]-g+dp[t][1][0]); dfs3(t,v); } } void dfs4(int v,int u){ m1[v] = m2[v] = 0; for(int i=0;i<tree[v].size();i++){ int t = tree[v][i]; if(t==u) continue; int g = num[t]>=k?1:0; if((dp[t][1][0]-g)>=m1[v]){ m2[v] = m1[v]; m1[v] = (dp[t][1][0]-g); } else{ if((dp[t][1][0]-g)>m2[v]){ m2[v] = (dp[t][1][0]-g); } } dfs3(t,v); } } int main() { while(cin>>n>>k){ memset(dp,-1,sizeof dp); for(int i=1;i<n;i++){ int x,y;cin>>x>>y; tree[x].push_back(y); tree[y].push_back(x); } dfs1(1,0); dfs(1,0); dfs3(1,0); dfs4(1,0); cout<<dfs2(1,0)<<endl; for(int i=1;i<=n;i++) tree[i].clear(); } return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Tree Separator |
User | cwlyzj |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2025 Byte |
Status | WA |
Exec Time | 116 ms |
Memory | 15744 KB |
Judge Result
Set Name | All | ||||
---|---|---|---|---|---|
Score / Max Score | 0 / 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 | 3 ms | 6400 KB |
00_sample_01 | AC | 3 ms | 6400 KB |
00_sample_02 | AC | 3 ms | 6400 KB |
00_sample_03 | AC | 3 ms | 6400 KB |
00_sample_04 | AC | 3 ms | 6400 KB |
00_sample_05 | AC | 3 ms | 6400 KB |
10_small_0 | AC | 3 ms | 6400 KB |
10_small_1 | AC | 3 ms | 6400 KB |
10_small_2 | WA | 3 ms | 6400 KB |
10_small_3 | AC | 3 ms | 6400 KB |
10_small_4 | AC | 3 ms | 6400 KB |
20_random_0 | AC | 72 ms | 8448 KB |
20_random_1 | AC | 9 ms | 6528 KB |
20_random_2 | AC | 116 ms | 9600 KB |
20_random_3 | AC | 34 ms | 7424 KB |
20_random_4 | AC | 13 ms | 6656 KB |
30_small_k_0 | WA | 56 ms | 7936 KB |
30_small_k_1 | WA | 64 ms | 8192 KB |
30_small_k_2 | WA | 23 ms | 7040 KB |
30_small_k_3 | WA | 84 ms | 8704 KB |
30_small_k_4 | WA | 105 ms | 9472 KB |
30_small_k_5 | WA | 15 ms | 6784 KB |
30_small_k_6 | WA | 59 ms | 8064 KB |
30_small_k_7 | WA | 32 ms | 7296 KB |
30_small_k_8 | WA | 30 ms | 7168 KB |
30_small_k_9 | WA | 62 ms | 8192 KB |
90_star_0 | AC | 90 ms | 9976 KB |
90_star_1 | AC | 91 ms | 9976 KB |
91_path_0 | AC | 108 ms | 15744 KB |
91_path_1 | AC | 116 ms | 15104 KB |
92_star_like_0 | AC | 97 ms | 9852 KB |
92_star_like_1 | WA | 97 ms | 9852 KB |
92_star_like_2 | WA | 95 ms | 9852 KB |
92_star_like_3 | WA | 97 ms | 9852 KB |
92_star_like_4 | WA | 94 ms | 9852 KB |