# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
689952 | EthanKim8683 | Valley (BOI19_valley) | C++17 | 169 ms | 45748 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;
using I=int;
using B=bool;
using Lli=long long int;
const I N=100000;
const I LOGN=17;
const I S=N;
const I W=1e9;
const Lli MAX=1e18;
vector<pair<I,I>>adjs[N];
I w_arr[N-1];
I c_arr[S];
Lli lows[N];
Lli diss[N];
I deps[N];
pair<I,Lli>ancs[N][LOGN];
I bots[N-1];
I tbgs[N],teds[N];
I t=0;
void dfs(I a,I p,Lli dis=0,I dep=0){
tbgs[a]=t++;
diss[a]=dis,deps[a]=dep;
for(auto[b,i]:adjs[a])if(b!=p){
I w=w_arr[i];
bots[i]=b;
dfs(b,a,dis+w,dep+1);
lows[a]=min(lows[a],lows[b]+w);
}
for(auto[b,w]:adjs[a])if(b!=p)ancs[b][0]={a,dis-lows[a]};
# | 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... |