oj.uz

Submission #895533

# Submission time Handle Problem Language Result Execution time Memory
895533 2023-12-30T08:00:39 Z abcvuitunggio Training (IOI07_training) C++17
37 / 100
 13 ms 12892 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 (p[u]==lca(p[u],a[j])||p[u]==lca(p[u],b[j]))
                path[p[u]][pos[i]].push_back(j);
            if (i<child[u].size())
                c[j]+=dp[u][1<<i];
            if (i==10)
                c[j]+=dp[u][0];
        }
}
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];
}

Compilation message

training.cpp: In function 'void dfs2(int)':
training.cpp:39:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |             if (i<child[u].size())
      |                 ~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 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 11 ms 11352 KB Output is correct
2 Correct 13 ms 12892 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
0 / 9.0

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

Subtask #6
0 / 9.0

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

Subtask #7
0 / 9.0

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

Subtask #8
0 / 9.0

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

Subtask #9
0 / 9.0

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

Subtask #10
0 / 9.0

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

Subtask #11
0 / 9.0

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