oj.uz

Submission #967856

# Submission time Handle Problem Language Result Execution time Memory
967856 2024-04-23T02:52:02 Z doducanh Training (IOI07_training) C++14
100 / 100
 12 ms 4860 KB 
///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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 604 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 740 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 600 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 856 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 2 ms 1880 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2560 KB Output is correct
2 Correct 4 ms 1436 KB Output is correct
3 Correct 3 ms 1796 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1116 KB Output is correct
2 Correct 2 ms 1784 KB Output is correct
3 Correct 12 ms 4856 KB Output is correct
4 Correct 3 ms 1884 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2304 KB Output is correct
2 Correct 9 ms 4860 KB Output is correct
3 Correct 4 ms 2048 KB Output is correct
4 Correct 4 ms 1684 KB Output is correct