Submission #697297

#	Time	Username	Problem	Language	Result	Execution time	Memory
697297		vjudge1	Training (IOI07_training)	C++14	100 / 100	50 ms	4564 KiB

training

#include<bits/stdc++.h>
#define F(i) ((1<<k[i])-1)
using namespace std;
const int N=1005,B=5005;
int n,m,x[B],y[B],w[B],f[N][1<<10],fa[N],dep[N],k[N],id[N],h[N],tot,sum;
struct edge {int to,nxt;}e[N<<1];
vector<int> a[N];
void add(int u,int v)
{
	e[++tot]={v,h[u]};
	h[u]=tot;
}
void dfs(int u)
{
	dep[u]=dep[fa[u]]+1;
	for(int i=h[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==fa[u]) continue;
		fa[v]=u;id[v]=k[u]++;dfs(v);
	}
}
int lca(int x,int y)
{
	while(x!=y)
	{
		if(dep[x]<dep[y]) swap(x,y);
		x=fa[x];
	}
	return x;
}
void DP(int u)
{
	for(int i=h[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==fa[u]) continue;
		DP(v);
		for(int j=0;j<(1<<id[v]);j++)
			f[u][j+(1<<id[v])]=f[u][j]+f[v][F(v)];
	}
	for(int i:a[u])
	{
		int s=0,sum=w[i];
		for(int T=0;T<=1;T++)
		{
			int p=x[i];
			if(p!=u)
			{
				sum+=f[p][F(p)];
				while(fa[p]!=u)
				{
					sum+=f[fa[p]][F(fa[p])-(1<<id[p])];
					p=fa[p];
				}
				s+=(1<<id[p]);
			}
			swap(x[i],y[i]);
		}
		for(int j=0;j<=F(u);j++)
		{
			if((j&s)==s) f[u][j]=max(f[u][j],f[u][j^s]+sum);
			for(int l=0;l<k[u];l++) if((j>>l)&1) f[u][j]=max(f[u][j],f[u][j-(1<<l)]);
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x[i],&y[i],&w[i]);
		if(w[i]==0) 
		{
			add(x[i],y[i]);
			add(y[i],x[i]);	
		}
		sum+=w[i];
	}
	dfs(1);
	for(int i=1;i<=m;i++)
	{
		if(w[i]==0||(dep[x[i]]+dep[y[i]])%2) continue;
		a[lca(x[i],y[i])].push_back(i);
	}
	DP(1);
	printf("%d",sum-f[1][F(1)]);
	return 0;
}

Compilation message (stderr)

training.cpp: In function 'int main()':
training.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
training.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |   scanf("%d%d%d",&x[i],&y[i],&w[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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