# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
434198 | dqhungdl | Road Closures (APIO21_roads) | C++17 | 2089 ms | 20192 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 "roads.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
const int MAX=1e5+5;
const long long INF=1e18;
vector<long long> f0,f1; // f0: do not need to close parent edge, f1: force to close parent edge (f0[u] >= f1[u])
vector<ii> g[MAX];
void dfs(int u,int p,int atMost) {
long long sum=0,minSum=0;
for(ii edge:g[u]) {
int v=edge.first,w=edge.second;
if(v==p)
continue;
dfs(v,u,atMost);
sum+=f0[v];
minSum+=min(f0[v],f1[v]+w);
}
int eraseNum=(int)g[u].size()-atMost;
if(eraseNum<=0) {
f0[u]=f1[u]=minSum;
return;
}
vector<long long> gaps;
for(ii edge:g[u]) {
int v=edge.first,w=edge.second;
if(v==p)
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... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |