oj.uz

Submission #778695

# Submission time Handle Problem Language Result Execution time Memory
778695 2023-07-10T15:04:39 Z PoonYaPat Training (IOI07_training) C++14
100 / 100
 10 ms 4588 KB 
#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.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
7.0 / 7.0

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

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1236 KB Output is correct
2 Correct 2 ms 1236 KB Output is correct
3 Correct 2 ms 1620 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2388 KB Output is correct
2 Correct 4 ms 1560 KB Output is correct
3 Correct 3 ms 2084 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 852 KB Output is correct
2 Correct 2 ms 1620 KB Output is correct
3 Correct 8 ms 4588 KB Output is correct
4 Correct 3 ms 1748 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2132 KB Output is correct
2 Correct 10 ms 4564 KB Output is correct
3 Correct 6 ms 1876 KB Output is correct
4 Correct 3 ms 1748 KB Output is correct