oj.uz

Submission #697246

# Submission time Handle Problem Language Result Execution time Memory
697246 2023-02-09T00:49:28 Z vjudge1 Training (IOI07_training) C++17
100 / 100
 15 ms 6892 KB 
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10,M=5e3+10;
vector<int>ed[N];
int n,m,dp[N][1<<9],X[M],Y[M],W[M],num[N][N];
int f[N],dfn[N],id[N],dep[N],ct;
struct node{
    int num,val;
    bool operator<(const node b)const{
        return val<b.val;
    }
};
struct RMQ{
    node st[N][21];
    RMQ(){}
    RMQ(int a[],int len){
        for(int i=1;i<=len;i++)st[i][0]=node{a[i],dep[a[i]]};
        for(int o=1;o<=20;o++){
            for(int i=1;i+(1<<o)-1<=len;i++){
                st[i][o]=min(st[i][o-1],st[i+(1<<(o-1))][o-1]);
            }
        }
    }
    int query(int l,int r){
        if(l==r)return l;
        if(id[l]>id[r])swap(l,r);
        l=id[l]+1,r=id[r];
        int len=r-l+1,k=__lg(len);
        return f[min(st[l][k],st[r-(1<<k)+1][k]).num];
    }
}ty;
void dfs(int x,int fa){
    f[x]=fa;
    dfn[++ct]=x;
    id[x]=ct;
    dep[x]=dep[fa]+1;
    for(int v:ed[x]){
        if(v==fa)continue;
        dfs(v,x);
    }
}
int dis(int x,int y){
    return dep[x]+dep[y]-dep[ty.query(x,y)]*2;
}
tuple<int,int,int>calc(int x,int y){
    int lca=ty.query(x,y),res=0;
    if(x!=lca)while(f[x]!=lca){
        res+=dp[f[x]][1<<num[f[x]][x]];
        x=f[x];
    }
    if(y!=lca)while(f[y]!=lca){
        res+=dp[f[y]][1<<num[f[y]][y]];
        y=f[y];
    }
    return {x,y,res};
}
vector<tuple<int,int,int>>vec[N];
void solve(int x,int fa){
    int sz=0;
    vector<int>son;
    for(int v:ed[x]){
        if(v==fa)continue;
        solve(v,x);
        num[x][v]=sz;
        sz++;
        son.push_back(v);
    }
    num[x][x]=-1;
    for(int i=0;i<1<<sz;i++){
        for(int o=0;o<sz;o++){
            if(!(i&(1<<o)))dp[x][i]+=dp[son[o]][0];
        }
    }
    for(auto [p,q,w]:vec[x]){
        auto [s1,s2,res]=calc(p,q);
        int val=res+w;
        if(p!=x)val+=dp[p][0];
        if(q!=x)val+=dp[q][0];
        s1=num[x][s1],s2=num[x][s2];
        if(s1>s2)swap(s1,s2);
        if(s1==-1){
            for(int i=0;i<1<<sz;i++){
                if((i&(1<<s2)))dp[x][i^(1<<s2)]=max(dp[x][i^(1<<s2)],dp[x][i]+val);
            }
        }
        else{
            for(int i=0;i<1<<sz;i++){
                if((i&(1<<s1))&&(i&(1<<s2)))dp[x][i^(1<<s1)^(1<<s2)]=max(dp[x][i^(1<<s1)^(1<<s2)],dp[x][i]+val);
            }
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    int ans=0;
    for(int i=1;i<=m;i++)scanf("%d%d%d",&X[i],&Y[i],&W[i]),ans+=W[i];
    for(int i=1;i<=m;i++)if(!W[i])ed[X[i]].push_back(Y[i]),ed[Y[i]].push_back(X[i]);
    dfs(1,0);
    ty=RMQ(dfn,n);
    for(int i=1;i<=m;i++)if(W[i]&&!(dis(X[i],Y[i])&1))vec[ty.query(X[i],Y[i])].emplace_back(X[i],Y[i],W[i]);
    solve(1,0);
    printf("%d",ans-dp[1][0]);
    return 0;
}

Compilation message

training.cpp: In function 'int main()':
training.cpp:94:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
training.cpp:96:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |     for(int i=1;i<=m;i++)scanf("%d%d%d",&X[i],&Y[i],&W[i]),ans+=W[i];
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
7.0 / 7.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3220 KB Output is correct
2 Correct 2 ms 3156 KB Output is correct
3 Correct 4 ms 3540 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6100 KB Output is correct
2 Correct 6 ms 5344 KB Output is correct
3 Correct 4 ms 5592 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2960 KB Output is correct
2 Correct 3 ms 3600 KB Output is correct
3 Correct 15 ms 6868 KB Output is correct
4 Correct 3 ms 3668 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6112 KB Output is correct
2 Correct 10 ms 6892 KB Output is correct
3 Correct 6 ms 5720 KB Output is correct
4 Correct 6 ms 5576 KB Output is correct