oj.uz

Submission #523659

# Submission time Handle Problem Language Result Execution time Memory
523659 2022-02-08T03:03:51 Z Fake4Fun Training (IOI07_training) C++14
100 / 100
 25 ms 16236 KB 
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int N=1e3+3, M=4e3+3;
int n,m;
int id,u[M],v[M],w[M];
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];
    int ans;
    if(o==low) ans=dp(o,0);
    else{
        int nxt=way[o][low];
        ans=dp(o,mp[o][nxt])+solve(nxt,low);
    }
    return f2[o][low]=ans;
}
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 3 ms 8396 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 4 ms 8652 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 15780 KB Output is correct
2 Correct 21 ms 15736 KB Output is correct

Subtask #4
7.0 / 7.0

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

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8396 KB Output is correct
2 Correct 3 ms 8524 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 4 ms 8928 KB Output is correct

Subtask #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10956 KB Output is correct
2 Correct 9 ms 10828 KB Output is correct
3 Correct 12 ms 11384 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14304 KB Output is correct
2 Correct 18 ms 13184 KB Output is correct
3 Correct 9 ms 13680 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10656 KB Output is correct
2 Correct 7 ms 11516 KB Output is correct
3 Correct 22 ms 16236 KB Output is correct
4 Correct 7 ms 11588 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14080 KB Output is correct
2 Correct 23 ms 15668 KB Output is correct
3 Correct 15 ms 13748 KB Output is correct
4 Correct 18 ms 13516 KB Output is correct