Submission #967856

#	Time	Username	Problem	Language	Result	Execution time	Memory
967856		doducanh	Training (IOI07_training)	C++14	100 / 100	12 ms	4860 KiB

training

///breaker
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e3+7;
int n,m;
int p[20][maxn];
int dp[maxn][1<<10];
int h[maxn];int deg[maxn];
int order[maxn];
pair<int,int>par[maxn];
vector<int>adj[maxn];
int cnt=0;
struct Edge
{
    int a,b,w,lca;
    bool operator <(const Edge b)const{
        return order[lca]<order[b.lca];
    }
};
vector<Edge>edges;
int lca(int u,int v)
{
    if(h[u]<h[v])swap(u,v);
    int k=h[u]-h[v];
    for(int i=0;i<=10;i++){
        if((k>>i)&1)u=p[i][u];
    }
    if(u==v)return u;
    for(int i=10;i>=0;i--){
        if(p[i][u]!=p[i][v]){
            u=p[i][u];
            v=p[i][v];
        }
    }
    return p[0][u];
}
void dfs(int u,int pa)
{
    h[u]=h[pa]+1;
    for(int v:adj[u])if(v!=pa){
        p[0][v]=u;
        par[v]={u,(1<<(deg[u]++))};
        dfs(v,u);
    }
    order[u]=++cnt;
}

void solve()
{
    for(auto ed:edges){
        int a=ed.a,b=ed.b,cur=ed.w,lca=ed.lca;
        if(((h[a]&1)!=(h[b]&1))&&cur!=0)continue;
        int mask1=0,mask2=0;
        for(mask1=0;a!=lca;tie(a,mask1)=par[a]){
            cur+=dp[a][mask1];
//            cout<<a;
        }
        for(mask2=0;b!=lca;tie(b,mask2)=par[b])cur+=dp[b][mask2];
        mask1|=mask2;
        for(int mask=(1<<deg[lca])-1;mask>=0;mask--){
            if(mask&mask1)continue;
            dp[lca][mask]=max(dp[lca][mask],cur+dp[lca][mask|mask1]);
        }
    }
}
void sol()
{
   cin>>n>>m;
   int sum=0;
   for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        if(!c){
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        sum+=c;
        edges.push_back({a,b,c,0});
   }
   p[0][1]=1;
   par[1]={1,0};
   dfs(1,1);
   for(int k=1;k<=10;k++){
       for(int i=1;i<=n;i++){
            p[k][i]=p[k-1][p[k-1][i]];
       }
   }
//   cout<<par[1].first<<"\n";
   for(auto &ed:edges){
       int a=ed.a,b=ed.b,cur=ed.w;
       if(((h[a]&1)!=(h[b]&1))&&cur!=0)continue;
       ed.lca=lca(a,b);
   }
   sort(edges.begin(),edges.end());
   solve();
   cout<<sum-dp[1][0];
}
main()
{
   ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
   sol();
}

Compilation message (stderr)

training.cpp:99:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   99 | main()
      | ^~~~

• 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