oj.uz

Submission #895515

# Submission time Handle Problem Language Result Execution time Memory
895515 2023-12-30T07:04:19 Z abcvuitunggio Training (IOI07_training) C++17
20 / 100
 18 ms 43100 KB 
#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);
}

Compilation message

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 41300 KB Output is correct
2 Correct 6 ms 41308 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 41300 KB Output is correct
2 Correct 6 ms 41484 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 16988 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 41240 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 41308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 41564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 43100 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 8028 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 13148 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 6492 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 13660 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -