Submission #895542

#	Time	Username	Problem	Language	Result	Execution time	Memory
895542		abcvuitunggio	Training (IOI07_training)	C++17	100 / 100	17 ms	15196 KiB

training

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 7 / 7
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9