# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
313819 | 2020-10-17T06:22:52 Z | BeanZ | Dynamite (POI11_dyn) | C++14 | 1997 ms | 36984 KB |
// I_Love_LPL #include <bits/stdc++.h> using namespace std; #define ll int #define endl '\n' const int N = 3e5 + 5; ll cnt = 0, mid; ll dp[N], hp[N], a[N], farcry[N]; vector<ll> node[N]; void dfs(ll u, ll p){ hp[u] = 0; for (auto j : node[u]){ if (j == p) continue; dfs(j, u); farcry[u] = min(farcry[u], farcry[j] + 1); } if (a[u] == 1 && farcry[u] > mid) hp[u] = 1, dp[u] = 0; for (auto j : node[u]){ if (j == p) continue; if (hp[j]){ if ((farcry[u] + dp[j] + 1) <= mid) continue; else dp[u] = max(dp[u], dp[j] + 1), hp[u] = 1; } } if (dp[u] == mid){ cnt++; dp[u] = -1e9; farcry[u] = 0; hp[u] = 0; } if (u == 1){ if (dp[u] == 0 && a[u] && farcry[u] > mid) cnt++; else if (dp[u] >= 1) cnt++; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); if (fopen("A.inp", "r")){ freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout); } ll n, m; cin >> n >> m; ll res = 0; for (int i = 1; i <= n; i++){ cin >> a[i]; if (a[i] == 1) res++; } for (int i = 1; i < n; i++){ ll u, v; cin >> u >> v; node[u].push_back(v); node[v].push_back(u); } if (res <= m) return cout << 0, 0; ll l = 1, h = n; while (l <= h){ mid = (l + h) >> 1; cnt = 0; memset(hp, 0, sizeof(hp)); for (int i = 1; i <= n; i++) farcry[i] = 1e9, dp[i] = -1e9; dfs(1, 1); if (cnt > m) l = mid + 1; else h = mid - 1; } cout << l; } /* */
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 7424 KB | Output is correct |
2 | Correct | 5 ms | 7424 KB | Output is correct |
3 | Correct | 6 ms | 8576 KB | Output is correct |
4 | Correct | 6 ms | 8576 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 8608 KB | Output is correct |
2 | Correct | 6 ms | 8576 KB | Output is correct |
3 | Correct | 6 ms | 8576 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 8576 KB | Output is correct |
2 | Correct | 7 ms | 8576 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 8576 KB | Output is correct |
2 | Correct | 7 ms | 8576 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 18 ms | 9088 KB | Output is correct |
2 | Correct | 40 ms | 9636 KB | Output is correct |
3 | Correct | 46 ms | 9856 KB | Output is correct |
4 | Correct | 56 ms | 11520 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 74 ms | 11008 KB | Output is correct |
2 | Correct | 172 ms | 11768 KB | Output is correct |
3 | Correct | 304 ms | 12152 KB | Output is correct |
4 | Correct | 265 ms | 14968 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 297 ms | 13048 KB | Output is correct |
2 | Correct | 311 ms | 13304 KB | Output is correct |
3 | Correct | 397 ms | 12920 KB | Output is correct |
4 | Correct | 504 ms | 18064 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 921 ms | 17656 KB | Output is correct |
2 | Correct | 1039 ms | 19272 KB | Output is correct |
3 | Correct | 1602 ms | 26872 KB | Output is correct |
4 | Correct | 1576 ms | 26744 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1883 ms | 24188 KB | Output is correct |
2 | Correct | 1546 ms | 26988 KB | Output is correct |
3 | Correct | 1864 ms | 31480 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1865 ms | 30472 KB | Output is correct |
2 | Correct | 1554 ms | 26916 KB | Output is correct |
3 | Correct | 1997 ms | 36984 KB | Output is correct |
4 | Correct | 655 ms | 27240 KB | Output is correct |