oj.uz

Submission #732824

# Submission time Handle Problem Language Result Execution time Memory
732824 2023-04-29T10:24:49 Z vjudge1 Beads and wires (APIO14_beads) C++17
28 / 100
 1000 ms 5884 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
using pii=pair<int,int>;
using pli=pair<long long,int>;
//using pll=pair<long long,long long>
const int maxn=2e5+9;
vector<pii>a[maxn];
int p[maxn];
const long long inf=-2e9-7;
long long dp[maxn][2];
long long f[maxn][2];
void dfs1(int u,int par){
p[u]=par;
dp[u][1]=inf;
dp[u][0]=0;
for (auto v:a[u]){
    if (v.fi==par)continue;
    dfs1(v.fi,u);
    //dp[v.fi][1]+=v.se;
    dp[u][0]+=max(dp[v.fi][1]+v.se,dp[v.fi][0]);
    //if (u==7)cout<<dp[v.fi][1]+v.se<<" "<<dp[v.fi][0]<<'\n';
}
long long choose=inf,notchoose=0;
for (auto v:a[u]){
    if (v.fi==par)continue;
    choose=max(choose+max(dp[v.fi][0],dp[v.fi][1]+v.se),notchoose+dp[v.fi][0]+v.se);
    notchoose=notchoose+max(dp[v.fi][0],dp[v.fi][1]+v.se);
}
dp[u][1]=choose;
}
void dfs2(int u,int par){
f[u][0]=0;
f[u][1]=inf;
for (auto v:a[u]){
    if (v.fi==par)continue;
    dfs2(v.fi,u);
    f[v.fi][1]+=v.se;
    f[u][0]+=max(f[v.fi][1],f[v.fi][0]);
}
long long choose=inf,notchoose=0;
for (auto v:a[u]){
    if (v.fi==par)continue;
    choose=max(choose+max(f[v.fi][0],f[v.fi][1]),notchoose+f[v.fi][0]+v.se);
    notchoose=notchoose+max(f[v.fi][0],f[v.fi][1]);
    //if (u==1)cout<<choose<<" "<<notchoose<<'\n';
}
f[u][1]=choose;
}
signed main(){
    srand(time(0));
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(".INP","r",stdin);
    //freopen(".OUT","w",stdout);
    int n;
    cin>>n;
    for1(i,1,n-1){
    int u,v,w;
    cin>>u>>v>>w;
    a[u].pb({v,w});
    a[v].pb({u,w});
    }
    dfs1(1,0);
    //cout<<dp[2][1];
    long long ans=dp[1][0];
    for1(i,1,n){
    for (auto v:a[i]){
        if (v.fi==p[i]){
           dfs2(v.fi,i);
        }
    }
    long long value=0;
    for (auto v:a[i]){
        if (v.fi==p[i]){
        value+=max(f[v.fi][0],f[v.fi][1]+v.se);
        }
        else {
        value+=max(dp[v.fi][0],dp[v.fi][1]+v.se);
        }
    }
    //cout<<value<<'\n';
    for1(j,0,sz(a[i])-1){
    for1(k,j+1,sz(a[i])-1){
    long long newvalue=value;
    int v1=a[i][j].fi,v2=a[i][k].fi;
    if (v1==p[i])newvalue-=max(f[v1][0],f[v1][1]+a[i][j].se)-f[v1][0];
    else newvalue-=max(dp[v1][0],dp[v1][1]+a[i][j].se)-dp[v1][0];
    if (v2==p[i])newvalue-=max(f[v2][0],f[v2][1]+a[i][k].se)-f[v2][0];
    else newvalue-=max(dp[v2][0],dp[v2][1]+a[i][k].se)-dp[v2][0];
    newvalue+=a[i][j].se+a[i][k].se;
    //cout<<newvalue<<'\n';
    //cout<<v1<<" "<<v2<<" "<<max(dp[v1][0],dp[v1][1]+a[i][j].se)+dp[v1][0]<<" "<<max(dp[v2][0],dp[v2][1]+a[i][k].se)+dp[v2][0]<<'\n';
    ans=max(ans,newvalue);
    }
    }
    }
    cout<<ans;

}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 5020 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 5024 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 5020 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 5024 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 4 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 4 ms 4948 KB Output is correct
17 Correct 4 ms 4948 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 4 ms 5020 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 4 ms 5028 KB Output is correct
22 Correct 4 ms 4948 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 5020 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 5024 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 4 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 4 ms 4948 KB Output is correct
17 Correct 4 ms 4948 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 4 ms 5020 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 4 ms 5028 KB Output is correct
22 Correct 4 ms 4948 KB Output is correct
23 Correct 667 ms 5448 KB Output is correct
24 Correct 654 ms 5460 KB Output is correct
25 Correct 661 ms 5460 KB Output is correct
26 Execution timed out 1066 ms 5884 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 5020 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 5024 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 4 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 4 ms 4948 KB Output is correct
17 Correct 4 ms 4948 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 4 ms 5020 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 4 ms 5028 KB Output is correct
22 Correct 4 ms 4948 KB Output is correct
23 Correct 667 ms 5448 KB Output is correct
24 Correct 654 ms 5460 KB Output is correct
25 Correct 661 ms 5460 KB Output is correct
26 Execution timed out 1066 ms 5884 KB Time limit exceeded
27 Halted 0 ms 0 KB -