oj.uz

Submission #697297

# Submission time Handle Problem Language Result Execution time Memory
697297 2023-02-09T07:13:50 Z vjudge1 Training (IOI07_training) C++14
100 / 100
 50 ms 4564 KB 
#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

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.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
7.0 / 7.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

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

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2004 KB Output is correct
2 Correct 23 ms 1024 KB Output is correct
3 Correct 5 ms 1388 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 648 KB Output is correct
2 Correct 3 ms 1492 KB Output is correct
3 Correct 50 ms 4308 KB Output is correct
4 Correct 4 ms 1620 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2004 KB Output is correct
2 Correct 29 ms 4348 KB Output is correct
3 Correct 18 ms 1520 KB Output is correct
4 Correct 25 ms 1260 KB Output is correct