Submission #697357

#	Time	Username	Problem	Language	Result	Execution time	Memory
697357		vjudge1	Training (IOI07_training)	C++17	100 / 100	19 ms	4508 KiB

training

#include<bits/stdc++.h>
using namespace std;
const int N=1050;
int n,m,num,ans,sum,dep[N],f[N][N],s[N][11],fa[N],cnt[N],p[N];
vector<int>v[N],t[N];
struct edge{int x,y,w,xt,yt;}e[N*5];
void dfs(int x,int y)
{
    for(int i:v[x])
        if(i!=y)
            fa[i]=x,p[i]=cnt[x],s[x][cnt[x]++]=i,
            dep[i]=dep[x]+1,dfs(i,x);
}
void solve(int x)
{
    for(int i=0;i<cnt[x];i++)
        solve(s[x][i]);
    for(int i:t[x])
    {
        int res=0,xx=e[i].x,yy=e[i].y;
        if(x==xx)
        {
            res+=f[yy][(1<<cnt[yy])-1];
            while(fa[yy]!=x)res+=f[fa[yy]][((1<<cnt[fa[yy]])-1)^(1<<p[yy])],yy=fa[yy];
        }
        else
        {
            res+=f[xx][(1<<cnt[xx])-1];
            res+=f[yy][(1<<cnt[yy])-1];
            while(fa[xx]!=x)res+=f[fa[xx]][((1<<cnt[fa[xx]])-1)^(1<<p[xx])],xx=fa[xx];
            while(fa[yy]!=x)res+=f[fa[yy]][((1<<cnt[fa[yy]])-1)^(1<<p[yy])],yy=fa[yy];
        }
        e[i].w+=res,e[i].xt=xx,e[i].yt=yy;
        // cout<<x<<' '<<e[i].x<<' '<<e[i].y<<' '<<p[xx]<<' '<<p[yy]<<' '<<e[i].w<<endl;
    }
    for(int i=0;i<(1<<cnt[x]);i++)
        for(int j=0;j<cnt[x];j++)
            if((i>>j)&1)f[x][i]+=f[s[x][j]][(1<<cnt[s[x][j]])-1];
    for(int i=0;i<(1<<cnt[x]);i++)
    {
        for(int j:t[x])
        {
            if(e[j].xt==x&&(!((i>>p[e[j].yt])&1)))
                f[x][i|(1<<p[e[j].yt])]=max(f[x][i|(1<<p[e[j].yt])],f[x][i]+e[j].w);
            else if((!((i>>p[e[j].yt])&1))&&(!((i>>p[e[j].xt])&1)))
                f[x][i|(1<<p[e[j].yt])|(1<<p[e[j].xt])]=
                max(f[x][i|(1<<p[e[j].yt])|(1<<p[e[j].xt])],f[x][i]+e[j].w);
        }
    }
    // cout<<x<<' '<<f[x][(1<<cnt[x])-1]<<endl;
}
signed main()
{
    scanf("%d%d",&n,&m);
    for(int i=1,x,y,z;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        if(z==0)v[x].push_back(y),v[y].push_back(x);
        else e[++num]={x,y,z,0,0};
    }
    dfs(1,0);
    for(int i=1;i<=num;i++)
    {
        if(dep[e[i].x]%2!=dep[e[i].y]%2)
            {ans+=e[i].w;continue;}
        sum+=e[i].w;
        if(dep[e[i].x]>dep[e[i].y])swap(e[i].x,e[i].y);
        int xx=e[i].x,yy=e[i].y;
        while(xx!=yy)
        {
            if(dep[xx]<dep[yy])
                swap(xx,yy);
            xx=fa[xx];
        }
        t[xx].push_back(i);
        // cout<<e[i].x<<' '<<e[i].y<<' '<<e[i].w<<' '<<xx<<endl;
    }
    // cout<<ans<<endl;
    solve(1);
    ans+=sum-f[1][(1<<cnt[1])-1];
    printf("%d\n",ans);
}

Compilation message (stderr)

training.cpp: In function 'int main()':
training.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
training.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         scanf("%d%d%d",&x,&y,&z);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

• 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