Submission #305378

#TimeUsernameProblemLanguageResultExecution timeMemory
305378caoashUntitled (POI11_dyn)C++14
10 / 100
1644 ms33272 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using vi = vector<int>; using vl = vector<ll>; #define pb push_back #define rsz resize #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() using pi = pair<int,int>; #define f first #define s second #define mp make_pair const int MX = 300005; const int MOD = (int) (1e9 + 7); const ll INF = (ll) 1e18; namespace output { void pr(int x) { cout << x; } void pr(long x) { cout << x; } void pr(ll x) { cout << x; } void pr(unsigned x) { cout << x; } void pr(unsigned long x) { cout << x; } void pr(unsigned long long x) { cout << x; } void pr(float x) { cout << x; } void pr(double x) { cout << x; } void pr(long double x) { cout << x; } void pr(char x) { cout << x; } void pr(const char * x) { cout << x; } void pr(const string & x) { cout << x; } void pr(bool x) { pr(x ? "true" : "false"); } template < class T1, class T2 > void pr(const pair < T1, T2 > & x); template < class T > void pr(const T & x); template < class T, class...Ts > void pr(const T & t, const Ts & ...ts) { pr(t); pr(ts...); } template < class T1, class T2 > void pr(const pair < T1, T2 > & x) { pr("{", x.f, ", ", x.s, "}"); } template < class T > void pr(const T & x) { pr("{"); // const iterator needed for vector<bool> bool fst = 1; for (const auto & a: x) pr(!fst ? ", " : "", a), fst = 0; pr("}"); } void ps() { pr("\n"); } // print w/ spaces template < class T, class...Ts > void ps(const T & t, const Ts & ...ts) { pr(t); if (sizeof...(ts)) pr(" "); ps(ts...); } void pc() { cout << "]" << endl; } // debug w/ commas template < class T, class...Ts > void pc(const T & t, const Ts & ...ts) { pr(t); if (sizeof...(ts)) pr(", "); pc(ts...); } #define dbg(x...) pr("[", #x, "] = ["), pc(x); } #ifdef LOCAL using namespace output; #endif int n, m; int d[MX]; vector<int> adj[MX]; int dp1[MX], dp2[MX]; int need = 0; void dfs(int v, int p, int mid) { dp1[v] = -1; dp2[v] = INT_MAX; for (int to : adj[v]) { if (to != p) { dfs(to, v, mid); if (dp1[to] != -1) { dp1[v] = max(dp1[v], dp1[to] + 1); } dp2[v] = min(dp2[v], dp2[to] + 1); } } if (dp1[v] == -1 && d[v]) { if (dp2[v] > mid) { dp1[v] = 0; } } if (dp1[v] == mid || (v == 0 && dp1[v] != -1)) { dp2[v] = 0; dp1[v] = -1; ++need; } return; } bool solve(int mid) { dfs(0, -1, mid); if (need > m) { return false; } return true; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; int cnt = 0; for (int i = 0; i < n; i++) { cin >> d[i]; cnt += d[i]; } for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; u--, v--; adj[u].pb(v), adj[v].pb(u); } int lo = 1, hi = n; int ans = 0; while (lo <= hi) { int mid = (lo + hi) / 2; need = 0; if (solve(mid)) { hi = mid - 1; ans = mid; } else { lo = mid + 1; } } if (m >= cnt) { cout << 0 << '\n'; } else { cout << ans << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...