Submission #1307259

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307259		Nipphitch	Training (IOI07_training)	C++20	100 / 100	36 ms	8948 KiB

training

// Credit : tphuocdz
#include <bits/stdc++.h>
using namespace std;
#define int long long 
const int K=10;
const int N=(1<<10);
const int INF=1e18;

int p[N+1],d[N+1],far[N+1][K+1],dp[N+1][N+1];
vector <pair <int,int>> adj[N+1];
vector <tuple <int,int,int>> k[N+1];

void cal(int u){
    for(int i=1;i<=K;i++){
        far[u][i]=far[far[u][i-1]][i-1];
    }
}

void dfs(int u,int par){
    d[u]=d[par]+1;
    far[u][0]=par;
    cal(u);
    p[u]=par;
    for(auto [v,w]:adj[u]){
        if(w>0 || v==par) continue;
        dfs(v,u);
    }
}

void goto_dep(int &a,int dep){
    if(d[a]==dep) return ;
    int akt=0;
    while(d[far[a][akt+1]]>dep) akt++;
    a=far[a][akt];
    goto_dep(a,dep);
}

int lca(int a,int b){
    if(d[a]>d[b]) swap(a,b);
    goto_dep(b,d[a]);
    while(a!=b){
        int akt=0;
        while(far[a][akt+1]!=far[b][akt+1]) akt++;
        a=far[a][akt];
        b=far[b][akt];
    }
    return a;
}

void fix(int u){
    vector <pair <int,int>> n;
    for(auto [v,w]:adj[u]){
        int l=lca(u,v);
        int dis=d[u]+d[v]-2*d[l];
        if(dis%2==0 || w==0){
            n.push_back({v,w});
            if(u<v && w>0) k[l].push_back({u,v,w});
        }
    }
    adj[u]=n;
}

int rec(int u,int pp,int x,pair <int,int> &dz){
    if(u==x){
        if(dz.first==-1) dz.first=pp;
        else dz.second=pp;
        return 0;
    }
    int idx=N-1,t=-1;
    for(auto [v,w]:adj[u]){
        t++;
        if(v==p[u] || w>0) continue;
        if(v==pp) idx-=(1<<t);
    }
    return dp[u][idx]-dp[pp][N-1]+rec(p[u],u,x,dz);
}

void solve(int u,int par){
    for(auto [v,w]:adj[u]){
        if(w>0 || v==par) continue;
        solve(v,u);
    }
    for(int i=0;i<N;i++){
        int t=-1;
        for(auto [v,w]:adj[u]){
            t++;
            if(v==par || w>0) continue;
            dp[u][i]+=dp[v][N-1];
        }
    }
    for(auto [a,b,val]:k[u]){
        pair <int,int> dz={-1,-1};
        int idx=0,w=rec(a,-1,u,dz)+rec(b,-1,u,dz),t=-1,odj=0;
        for(auto [v,w]:adj[u]){
            t++;
            if(v==par || w>0) continue;
            if(v==dz.first || v==dz.second){
                idx+=(1<<t);
                odj+=dp[v][N-1];
            }
        }
        for(int i=0;i<N;i++){
            if((i&idx)==idx){
                dp[u][i]=max(dp[u][i],dp[u][i^idx]+val-odj+w);
            }
        }
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    cin >> n >> m;
    int s=0;
    for(int i=0;i<m;i++){
        int u,v,w;
        cin >> u >> v >> w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
        s+=w;
    }
    dfs(1,1);
    for(int i=1;i<=n;i++) fix(i);
    solve(1,1);
    int ans=0;
    for(int i=0;i<N;i++) ans=max(ans,dp[1][i]);
    cout << s-ans;  
}

• 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