oj.uz

Submission #895542

# Submission time Handle Problem Language Result Execution time Memory
895542 2023-12-30T08:20:25 Z abcvuitunggio Training (IOI07_training) C++17
100 / 100
 17 ms 15196 KB 
#include <bits/stdc++.h>
using namespace std;
int n,m,a[5001],b[5001],c[5001],dp[1001][1024],f[1001][1001],p[1001],d[1001],res,pos[1001],mask[5001];
vector <int> ke[1001],ve[1001],child[1001],path[1001][11];
void dfs(int u, int par){
    for (int v:ke[u])
        if (v!=par){
            pos[v]=child[u].size();
            child[u].push_back(v);
            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]));
}
void dfs2(int u){
    for (int v:child[u]){
        dfs2(v);
        for (int i=0;i<(1<<(child[u].size()));i++)
            if (!((i>>pos[v])&1))
                dp[u][i]+=dp[v][0];
    }
    for (int i=(1<<(child[u].size()))-1;i>=0;i--)
        for (int j:ve[u])
            if (!(mask[j]&i))
                dp[u][i]=max(dp[u][i],dp[u][i|mask[j]]+c[j]);
    for (int i=0;i<=10;i++)
        for (int j:path[u][i]){
            if (u!=lca(a[j],b[j]))
                path[p[u]][pos[u]].push_back(j);
            c[j]+=dp[u][(1<<i)&1023];
        }
}
int 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]);
            if (a[i]!=l)
                path[a[i]][10].push_back(i);
            if (b[i]!=l)
                path[b[i]][10].push_back(i);
            for (int v:child[l])
                if (v==lca(v,a[i])||v==lca(v,b[i]))
                    mask[i]|=(1<<pos[v]);
            ve[l].push_back(i);
        }
    dfs2(1);
    cout << res-dp[1][0];
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2920 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10588 KB Output is correct
2 Correct 10 ms 11104 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3164 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Correct 2 ms 3216 KB Output is correct
3 Correct 5 ms 4444 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6748 KB Output is correct
2 Correct 6 ms 5784 KB Output is correct
3 Correct 5 ms 5980 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3160 KB Output is correct
2 Correct 3 ms 4440 KB Output is correct
3 Correct 17 ms 15196 KB Output is correct
4 Correct 4 ms 5208 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8536 KB Output is correct
2 Correct 17 ms 15196 KB Output is correct
3 Correct 9 ms 9820 KB Output is correct
4 Correct 7 ms 5976 KB Output is correct