oj.uz

Submission #523653

# Submission time Handle Problem Language Result Execution time Memory
523653 2022-02-08T02:59:58 Z Fake4Fun Training (IOI07_training) C++14
54 / 100
 18 ms 15752 KB 
//source: https://oj.uz/problem/view/IOI07_training

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int N=1e3+3;
int n,m;
int id,u[N],v[N],w[N];
int dad[N],h[N];
int way[N][N],mp[N][N];
vector<int> adj[N],edge[N];
void DFS(int u){
    h[u]=h[dad[u]]+1;
    int x=u, cc=0;
    way[x][u]=x;
    while(x!=1){
        way[dad[x]][u]=x;
        x=dad[x];
    }
    for(auto i:adj[u]) if(i!=dad[u]){
        mp[u][i]=1<<cc; ++cc;
        dad[i]=u, DFS(i);
    }
}
int LCA(int u,int v){
    while(u!=v){
        if(h[u]<h[v]) swap(u,v);
        u=dad[u];
    }
    return u;
}
int f1[N][1024],f2[N][N];
int dp(int o,int mask);
int solve(int o,int low){
    if(f2[o][low]!=-1) return f2[o][low];
    if(o==low) return f2[o][low]=dp(o,0);
    else{
        int nxt=way[o][low];
        return f2[o][low]=dp(o,mp[o][nxt])+solve(nxt,low);
    }
    return -1;
}
int dp(int o,int mask){
    if(f1[o][mask]!=-1) return f1[o][mask];
    int ans=0;
    for(auto i:adj[o])
        if(i!=dad[o]&&!(mask&mp[o][i])) ans+=dp(i,0);
    for(auto i:edge[o]){
        int l=way[o][u[i]], r=way[o][v[i]];
        if((mask&mp[o][l])||(mask&mp[o][r])) continue;
        int cur=w[i]+dp(o,mask|mp[o][l]|mp[o][r]);
        if(o!=l) cur+=solve(l,u[i]);
        if(o!=r) cur+=solve(r,v[i]);
        ans=max(ans,cur);
    }
    return f1[o][mask]=ans;
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m;
    int sum=0;
    while(m--){
        ++id;
        cin>>u[id]>>v[id]>>w[id];
        sum+=w[id];
        if(!w[id]){
            adj[u[id]].push_back(v[id]);
            adj[v[id]].push_back(u[id]);
            --id;
        }
    }
    DFS(1);
    for(int i=1;i<=id;i++){
        if((h[u[i]]+h[v[i]])%2) continue;
        edge[LCA(u[i],v[i])].push_back(i);
    }
    memset(f1,-1,sizeof(f1));
    memset(f2,-1,sizeof(f2));
    cout<<sum-dp(1,0);
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 15752 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
7.0 / 7.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

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

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 10888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 14144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 10564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 14072 KB Output isn't correct
2 Halted 0 ms 0 KB -