# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
162239 | HungAnhGoldIBO2020 | Beads and wires (APIO14_beads) | C++14 | 7 ms | 5112 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;
const int N=2e5+2;
const int inf=1e9+7;
vector<pair<int,int> > adj[N];
int dp[N][2][2][2];
void dfs(int x,int p,int val){
int max1=-inf,max2=-inf,max3=-inf;
for(auto j:adj[x]){
int i=j.first;
if(i!=p){
dfs(i,x,j.second);
dp[x][0][0][0]+=max(dp[i][0][0][0],dp[i][1][1][0]);
if(max1<max(dp[i][0][0][0],max(dp[i][0][0][1],dp[i][1][0][1]))-max(dp[i][0][0][0],dp[i][1][1][0])){
max1=max(dp[i][0][0][0],max(dp[i][0][0][1],dp[i][1][0][1]))-max(dp[i][0][0][0],dp[i][1][1][0]);
}
//for 0,0,1
if(max2<=max(dp[i][0][0][0],max(dp[i][0][0][1],dp[i][1][0][1]))-max(dp[i][1][1][0],dp[i][0][0][0])+j.second){
max3=max2;
max2=max(dp[i][0][0][0],max(dp[i][0][0][1],dp[i][1][0][1]))-max(dp[i][1][1][0],dp[i][0][0][0])+j.second;
}
else{
if(max3<max(dp[i][0][0][0],max(dp[i][0][0][1],dp[i][1][0][1]))-max(dp[i][1][1][0],dp[i][0][0][0])+j.second){
max3=max(dp[i][0][0][0],max(dp[i][0][0][1],dp[i][1][0][1]))-max(dp[i][1][1][0],dp[i][0][0][0])+j.second;
}
}
//for both 1,0,1 and 1,1,0
}
}
dp[x][0][0][1]=dp[x][0][0][0]+max1;
# | 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... |