Submission #3833636
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]); dp[v][0] = max(dp[v][0],dp[chi][1]+(size[chi]>1&&N-size[chi]>=K)); dp[v][0] = max(dp[v][0],dp[chi][1]+dp[v][1]+(size[v]>1&&N-size[v]>=K)); dp[v][1] = max(dp[v][1],dp[chi][1]+cnt[v]-(size[chi]>=K)); dp[v][1] = max(dp[v][1],cnt[v]-(size[chi]>=K)+cnt[chi]); } } 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); /* debugArray(size,N); debugArray(cnt,N); */ //debug(dp[2][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 | 0 |
Code Size | 1833 Byte |
Status | WA |
Exec Time | 52 ms |
Memory | 13952 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 | 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 | WA | 1 ms | 256 KB |
10_small_3 | WA | 1 ms | 256 KB |
10_small_4 | WA | 1 ms | 256 KB |
20_random_0 | WA | 30 ms | 5760 KB |
20_random_1 | WA | 4 ms | 768 KB |
20_random_2 | WA | 45 ms | 8704 KB |
20_random_3 | WA | 14 ms | 2944 KB |
20_random_4 | WA | 5 ms | 1152 KB |
30_small_k_0 | WA | 23 ms | 4608 KB |
30_small_k_1 | WA | 25 ms | 5120 KB |
30_small_k_2 | WA | 9 ms | 2048 KB |
30_small_k_3 | WA | 34 ms | 6656 KB |
30_small_k_4 | WA | 43 ms | 8320 KB |
30_small_k_5 | WA | 6 ms | 1408 KB |
30_small_k_6 | WA | 29 ms | 4864 KB |
30_small_k_7 | WA | 13 ms | 2688 KB |
30_small_k_8 | WA | 12 ms | 2560 KB |
30_small_k_9 | WA | 25 ms | 5120 KB |
90_star_0 | AC | 31 ms | 6904 KB |
90_star_1 | AC | 33 ms | 6904 KB |
91_path_0 | WA | 52 ms | 13952 KB |
91_path_1 | WA | 46 ms | 13440 KB |
92_star_like_0 | WA | 38 ms | 9084 KB |
92_star_like_1 | WA | 38 ms | 9084 KB |
92_star_like_2 | WA | 38 ms | 9084 KB |
92_star_like_3 | WA | 38 ms | 9084 KB |
92_star_like_4 | WA | 39 ms | 9084 KB |