这份代码有UB吗?
  • 板块学术版
  • 楼主UFOI
  • 当前回复4
  • 已保存回复5
  • 发布时间2024/1/18 20:39
  • 上次更新2024/1/19 08:14:27
查看原帖
这份代码有UB吗?
777756
UFOI楼主2024/1/18 20:39

rt,洛谷 AC,acc 过不去样例,但是放在洛谷上就能过。

#include<bits/stdc++.h>
using namespace std;
int n,x,idx,k,a[100001],dp[100001][3];
vector<int>G[100001];
void dfs(int rt,int fa){
    dp[rt][0]=a[rt];
    bool isu=0;
    for(int i=0;i<G[rt].size();i++){
        if(G[rt][i]==fa) continue;
        dfs(G[rt][i],rt);
        if(dp[G[rt][i]][0]<dp[G[rt][i]][1]) isu=1;
        dp[rt][0]+=min(dp[G[rt][i]][0],min(dp[G[rt][i]][1],dp[G[rt][i]][2]));
        dp[rt][1]+=min(dp[G[rt][i]][0],dp[G[rt][i]][1]);
        dp[rt][2]+=min(dp[G[rt][i]][0],dp[G[rt][i]][1]);
    }
    if(!isu){
        int p=998244353;
        for(int i=0;i<G[rt].size();i++) p=min(p,dp[G[rt][i]][0]-dp[G[rt][i]][1]);
        dp[rt][1]+=p;
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>idx>>a[idx]>>k;
        for(int j=1;j<=k;j++){
            cin>>x;
            G[idx].push_back(x);
            G[x].push_back(idx);
        }
    }
    dfs(1,0);
    cout<<min(dp[1][0],dp[1][1]);
}
2024/1/18 20:39
加载中...