oj.uz

Submission #65137

# Submission time Handle Problem Language Result Execution time Memory
65137 2018-08-06T17:12:36 Z edisonhello Training (IOI07_training) C++14
100 / 100
 52 ms 5464 KB 
#include<bits/stdc++.h>
using namespace std;

vector<int> Q;
vector<int> idx[1005];
vector<int> G[1005];
int p[1005],d[1005],dp[1005][1<<11],apx[1005],mx[1005];

void dfs1(int now,int pa,int dep){
    p[now]=pa;
    d[now]=dep;
    mx[now]=(1<<G[now].size())-1;
    for(int i=0;i<G[now].size();++i){
        if(G[now][i]==pa)continue;
        apx[G[now][i]]=i;
        dfs1(G[now][i],now,dep+1);
    }
}

void dfs2(int now,int pa){
    for(int i=0;i<G[now].size();++i){
        if(G[now][i]==pa)continue;
        dfs2(G[now][i],now);
    }
    for(int z=0;z<=mx[now];++z){
        for(int i=0;i<G[now].size();++i){
            if(G[now][i]==pa)continue;
            if(z&(1<<i))dp[now][z]+=dp[G[now][i]][mx[G[now][i]]];
        }
    }
    for(int i:idx[now]){
        int u=Q[i],v=Q[i+1],c=Q[i+2];
        if(v==now)swap(u,v);
        if(u==now){
            c+=dp[v][mx[v]];
            while(p[v]!=now){
                c+=dp[p[v]][mx[p[v]]^(1<<apx[v])];
                v=p[v];
            }
            Q[i]=u; Q[i+1]=v; Q[i+2]=c;
        }
        else{
            c+=dp[v][mx[v]]+dp[u][mx[u]];
            while(p[v]!=now){
                c+=dp[p[v]][mx[p[v]]^(1<<apx[v])];
                v=p[v];
            }
            while(p[u]!=now){
                c+=dp[p[u]][mx[p[u]]^(1<<apx[u])];
                u=p[u];
            }
            Q[i]=u; Q[i+1]=v; Q[i+2]=c;
        }
    }
    for(int z=0;z<=mx[now];++z){
        for(int i:idx[now]){
            int u=Q[i],v=Q[i+1],c=Q[i+2];
            // cout<<"(u,v,c): "<<u<<" "<<v<<" "<<c<<endl;
            if(u==now){
                if(z&(1<<apx[v]))dp[now][z]=max(dp[now][z],dp[now][z^(1<<apx[v])]+c);
            }
            else{
                if((z&(1<<apx[v]))&&(z&(1<<apx[u])))dp[now][z]=max(dp[now][z],dp[now][z^(1<<apx[v])^(1<<apx[u])]+c);
            }
        }
        // cout<<"dp["<<now<<"]["<<z<<"]: "<<dp[now][z]<<endl;
    }
}

int main(){
    int n,m; cin>>n>>m;
    int tot=0;
    while(m--){
        int u,v,c; cin>>u>>v>>c;
        tot+=c;
        if(!c){
            G[u].push_back(v);
            G[v].push_back(u);
        }
        else{
            Q.push_back(u);
            Q.push_back(v);
            Q.push_back(c);
        }
    }
    dfs1(1,0,1);
    for(int i=0;i<Q.size();i+=3){
        int u=Q[i],v=Q[i+1];
        while(d[u]>d[v])u=p[u];
        while(d[u]<d[v])v=p[v];
        while(u!=v)u=p[u],v=p[v];
        if((d[Q[i]]+d[Q[i+1]]-2*d[u])&1)continue;
        idx[u].push_back(i);
    }
    dfs2(1,0);
    cout<<tot-dp[1][mx[1]]<<endl;
}

Compilation message

training.cpp: In function 'void dfs1(int, int, int)':
training.cpp:13:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<G[now].size();++i){
                 ~^~~~~~~~~~~~~~
training.cpp: In function 'void dfs2(int, int)':
training.cpp:21:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<G[now].size();++i){
                 ~^~~~~~~~~~~~~~
training.cpp:26:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<G[now].size();++i){
                     ~^~~~~~~~~~~~~~
training.cpp: In function 'int main()':
training.cpp:87:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<Q.size();i+=3){
                 ~^~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 728 KB Output is correct
2 Correct 4 ms 908 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 4756 KB Output is correct
2 Correct 12 ms 4788 KB Output is correct

Subtask #4
7.0 / 7.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4788 KB Output is correct
2 Correct 7 ms 4788 KB Output is correct
3 Correct 17 ms 4788 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4788 KB Output is correct
2 Correct 31 ms 4788 KB Output is correct
3 Correct 10 ms 4788 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 4788 KB Output is correct
2 Correct 7 ms 4788 KB Output is correct
3 Correct 52 ms 5404 KB Output is correct
4 Correct 9 ms 5404 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 5404 KB Output is correct
2 Correct 28 ms 5464 KB Output is correct
3 Correct 21 ms 5464 KB Output is correct
4 Correct 25 ms 5464 KB Output is correct