Submission #523659

#	Time	Username	Problem	Language	Result	Execution time	Memory
523659		Fake4Fun	Training (IOI07_training)	C++14	100 / 100	25 ms	16236 KiB

training

#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 / 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