제출 #895515

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
895515		abcvuitunggio	Training (IOI07_training)	C++17	20 / 100	18 ms	43100 KiB

training

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[5001],b[5001],c[5001],dp[1001][5001],f[1001][1001],p[1001],d[1001],res;
vector <int> ke[1001],ve[1001],nodes[1001];
void dfs(int u, int par){
    for (int v:ke[u])
        if (v!=par){
            p[v]=u;
            d[v]=d[u]+1;
            dfs(v,u);
        }
}
int lca(int u, int v){
    if (!u||!v)
        return 0;
    if (u==v)
        return u;
    if (f[u][v])
        return f[u][v];
    return f[u][v]=(d[u]>d[v]?lca(p[u],v):lca(u,p[v]));
}
int calc(int u, int i){
    if (dp[u][i]!=-1)
        return dp[u][i];
    int mx=0,sum=0,w=0;
    for (int v:ke[u])
        if (v!=p[u]){
            if (v==lca(v,a[i])||v==lca(v,b[i]))
                w=v;
            sum+=calc(v,i*(v==w));
        }
    mx=sum;
    for (int j:ve[u])
        if (!w||w!=lca(w,a[j])&&w!=lca(w,b[j])){
            int s=sum+c[j];
            for (int v:nodes[j])
                s=s-calc(v,0)+calc(v,j);
            mx=max(mx,s);
        }
    return dp[u][i]=mx;
}
int32_t main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    cin >> n >> m;
    for (int i=1;i<=m;i++){
        cin >> a[i] >> b[i] >> c[i];
        res+=c[i];
        if (!c[i]){
            ke[a[i]].push_back(b[i]);
            ke[b[i]].push_back(a[i]);
        }
    }
    dfs(1,1);
    for (int i=1;i<=m;i++)
        if (c[i]&&(d[a[i]]^d[b[i]])%2==0){
            int l=lca(a[i],b[i]);
            for (int v:ke[l]){
                if (v!=p[l]&&(v==lca(v,a[i])||v==lca(v,b[i])))
                    nodes[i].push_back(v);
            }
            ve[l].push_back(i);
        }
    memset(dp,-1,sizeof(dp));
    cout << res-calc(1,0);
}

컴파일 시 표준 에러 (stderr) 메시지

training.cpp: In function 'long long int calc(long long int, long long int)':
training.cpp:35:31: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   35 |         if (!w||w!=lca(w,a[j])&&w!=lca(w,b[j])){
      |                 ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 7
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9