Submission #2474663
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 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)+f); int add = (m1[v]==(need[t]-g))?m2[v]:m1[v]; ans = max(ans,need[t]+need[v]-g+add+f); } return ans; } void dfs3(int v,int u){ //s[v] = 0; 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; //s[v] += dp[t][1][0]; if((need[t]-g)>=m1[v]){ m2[v] = m1[v]; m1[v] = need[t]-g; } else{ if(need[t]>m2[v]){ m2[v] = need[t]-g; } } dfs3(t,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 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); 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 | 1787 Byte |
Status | WA |
Exec Time | 107 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 | WA | 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 | WA | 3 ms | 6400 KB |
10_small_1 | WA | 3 ms | 6400 KB |
10_small_2 | WA | 3 ms | 6400 KB |
10_small_3 | WA | 3 ms | 6400 KB |
10_small_4 | WA | 3 ms | 6400 KB |
20_random_0 | WA | 69 ms | 8448 KB |
20_random_1 | WA | 9 ms | 6528 KB |
20_random_2 | WA | 106 ms | 9600 KB |
20_random_3 | WA | 33 ms | 7424 KB |
20_random_4 | WA | 13 ms | 6656 KB |
30_small_k_0 | WA | 54 ms | 8064 KB |
30_small_k_1 | WA | 61 ms | 8192 KB |
30_small_k_2 | WA | 22 ms | 7040 KB |
30_small_k_3 | WA | 80 ms | 8704 KB |
30_small_k_4 | WA | 100 ms | 9472 KB |
30_small_k_5 | WA | 14 ms | 6784 KB |
30_small_k_6 | WA | 57 ms | 8064 KB |
30_small_k_7 | WA | 31 ms | 7296 KB |
30_small_k_8 | WA | 28 ms | 7168 KB |
30_small_k_9 | WA | 59 ms | 8192 KB |
90_star_0 | AC | 94 ms | 9976 KB |
90_star_1 | AC | 90 ms | 9976 KB |
91_path_0 | WA | 107 ms | 15744 KB |
91_path_1 | WA | 103 ms | 15104 KB |
92_star_like_0 | WA | 96 ms | 9852 KB |
92_star_like_1 | AC | 97 ms | 9852 KB |
92_star_like_2 | WA | 94 ms | 9852 KB |
92_star_like_3 | WA | 94 ms | 9852 KB |
92_star_like_4 | AC | 94 ms | 9852 KB |