Submission #1200662

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200662		12345678	Training (IOI07_training)	C++20	100 / 100	7 ms	4680 KiB

training

#include <bits/stdc++.h>

using namespace std;

const int nx=1e3+5, kx=10;

int n, m, u, v, w, dp[nx][1<<kx], lvl[nx], pa[nx][kx], idx[nx], sz[nx], res;
vector<int> d[nx];
vector<tuple<int, int, int>> edg, event[nx];

void dfs(int u, int p)
{
    lvl[u]=lvl[p]+1;
    pa[u][0]=p;
    for (int i=1; i<kx; i++) pa[u][i]=pa[pa[u][i-1]][i-1];
    for (auto v:d[u]) if (v!=p) idx[v]=sz[u]++, dfs(v, u);
}

int lca(int u, int v)
{
    if (lvl[u]>lvl[v]) swap(u, v);
    for (int i=kx-1; i>=0; i--) if (lvl[pa[v][i]]>=lvl[u]) v=pa[v][i];
    if (u==v) return u;
    for (int i=kx-1; i>=0; i--) if (pa[u][i]!=pa[v][i]) u=pa[u][i], v=pa[v][i];
    return pa[u][0];
}

void solve(int u, int p)
{
    for (auto v:d[u]) if (v!=p) solve(v, u), dp[u][1<<idx[v]]=dp[v][(1<<sz[v])-1];
    for (auto [cu, cv, cw]:event[u])
    {
        int umsk=0, sm=0, pv=-1;
        while (cu!=u)
        {
            int msk=(1<<sz[cu])-1;
            if (pv!=-1) msk^=(1<<idx[pv]);
            pv=cu;
            sm+=dp[cu][msk];
            if (pa[cu][0]==u) umsk^=(1<<idx[cu]);
            cu=pa[cu][0];
        }
        pv=-1;
        while (cv!=u)
        {
            int msk=(1<<sz[cv])-1;
            if (pv!=-1) msk^=(1<<idx[pv]);
            pv=cv;
            sm+=dp[cv][msk];
            if (pa[cv][0]==u) umsk^=(1<<idx[cv]);
            cv=pa[cv][0];
        }
        dp[u][umsk]=max(dp[u][umsk], sm+cw);
    }
    for (int msk=0; msk<(1<<sz[u]); msk++) for (int j=msk; j>0; j=(j-1)&msk) dp[u][msk]=max(dp[u][msk], dp[u][j]+dp[u][msk^j]);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=m; i++)
    {
        cin>>u>>v>>w;
        if (!w) d[u].push_back(v), d[v].push_back(u);
        else edg.push_back({u, v, w});
    }
    dfs(1, 1);
    for (auto [u, v, w]:edg)
    {
        if ((lvl[u]+lvl[v]-2*lvl[lca(u, v)])%2) res+=w;
        else event[lca(u, v)].push_back({u, v, w}), res+=w;
    }
    solve(1, 1);
    cout<<res-dp[1][(1<<sz[1])-1];
}

• 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