Submission #778695

#	Time	Username	Problem	Language	Result	Execution time	Memory
778695		PoonYaPat	Training (IOI07_training)	C++14	100 / 100	10 ms	4588 KiB

training

#include <bits/stdc++.h>
using namespace std;

struct edg {
    int a,b,w;
};

int n,m,dp[1005][1<<10],level[1005],p[1005],ss,mmax[1005];
vector<int> adj[1005],adj2[1005];
vector<edg> edge,e[1005];

void dfs (int x, int par) {
    level[x]=level[par]+1;
    p[x]=par;
    for (auto s : adj[x]) if (s!=par) dfs(s,x), adj2[x].push_back(s);
}

void dfs2(int x) {
    int k=adj2[x].size();
    for (int i=0; i<k; ++i) {
        int s=adj2[x][i];
        dfs2(s);
        dp[x][1<<i]=dp[s][mmax[s]];
    }

    for (auto s : e[x]) {
        int a=s.a, b=s.b, sum=s.w, k1=-1, k2=-1;
        
        int now=p[a], pre=a;
        if (a!=x) {
            sum+=dp[pre][mmax[pre]];
            while (now!=x) {
                int k=lower_bound(adj2[now].begin(),adj2[now].end(),pre)-adj2[now].begin();
                sum+=dp[now][mmax[now]^(1<<k)];
                pre=now;
                now=p[now];
            }
            k1=lower_bound(adj2[x].begin(),adj2[x].end(),pre)-adj2[x].begin();
        }

        now=p[b]; pre=b;
        if (b!=x) {
            sum+=dp[pre][mmax[pre]];
            while (now!=x) {
                int k=lower_bound(adj2[now].begin(),adj2[now].end(),pre)-adj2[now].begin();
                sum+=dp[now][mmax[now]^(1<<k)];
                pre=now;
                now=p[now];
            }
            k2=lower_bound(adj2[x].begin(),adj2[x].end(),pre)-adj2[x].begin();
        }

        if (k1==-1) dp[x][1<<k2]=max(dp[x][1<<k2],sum);
        else if (k2==-1) dp[x][1<<k1]=max(dp[x][1<<k1],sum);
        else dp[x][(1<<k1)|(1<<k2)]=max(dp[x][(1<<k1)|(1<<k2)],sum);
    }

    for (int mask=1; mask<(1<<k); ++mask) {
        int st=-1;
        for (int j=0; j<k; ++j) {
            if (mask&(1<<j)) {
                if (st==-1) {
                    st=j;
                    dp[x][mask]=max(dp[x][mask],dp[x][1<<j]+dp[x][mask^(1<<j)]);
                } else {
                    dp[x][mask]=max(dp[x][mask],dp[x][(1<<st)|(1<<j)]+dp[x][mask^(1<<st)^(1<<j)]);
                }
            }
        }
    }
    
}

void solve(int X, int Y, int w) {
    int x=X, y=Y;
    if (level[x]<level[y]) swap(x,y);
    int dif=level[x]-level[y];
    while (dif--) x=p[x];
    while (x!=y) x=p[x],y=p[y];
    if ((level[X]+level[Y]-2*level[x])%2==0) e[x].push_back({X,Y,w});
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    for (int i=0; i<m; ++i) {
        int a,b,w; cin>>a>>b>>w;
        if (w==0) {
            adj[a].push_back(b);
            adj[b].push_back(a);
        } else edge.push_back({a,b,w});
        ss+=w;
    }
    dfs(1,0);
    for (int i=1; i<=n; ++i) sort(adj2[i].begin(),adj2[i].end()), mmax[i]=(1<<(adj2[i].size()))-1;
    for (auto s : edge) solve(s.a,s.b,s.w);
    dfs2(1);
    cout<<ss-dp[1][mmax[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