# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
527706 | joelau | Parkovi (COCI22_parkovi) | C++14 | 1361 ms | 37236 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
long long N,K, dp1[200005], dp2[200005], val, inf = 1e18;
vector< pair<long long,long long> > lst[200005];
bitset<200005> ans;
void dfs (long long x, long long p) {
dp1[x] = inf, dp2[x] = 0;
for (auto v: lst[x]) if (v.first != p) {
dfs(v.first,x);
dp1[x] = min(dp1[x],dp1[v.first] + v.second);
if (dp2[v.first] != -1) {
if (dp2[v.first] + v.second > val) ans[v.first] = 1, dp1[x] = min(dp1[x],v.second);
else dp2[x] = max(dp2[x],dp2[v.first] + v.second);
}
}
if (dp1[x] <= val) dp2[x] = -1;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> N >> K;
for (long long i = 0; i < N-1; ++i) {
long long u,v,w; cin >> u >> v >> w; u--, v--;
lst[u].emplace_back(v,w), lst[v].emplace_back(u,w);
}
long long low = -1, high = 2e14;
while (high - low > 1) {
val = (low+high)/2;
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |