Submission #986309

#	Time	Username	Problem	Language	Result	Execution time	Memory
986309		Pyqe	Training (IOI07_training)	C++17	100 / 100	37 ms	33748 KiB

training

#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define fr first
#define sc second

const long long inf=1e18;
long long n,m,ttl=0,nn=0,nm,wg[4069],pr[1069],dh[1069],ca[1069],dp[1069][4069],dp2[1ll<<10];
vector<long long> al[1069];
pair<long long,long long> ed[4069];
bitset<1069> vtd;
bitset<4069> spc[1069];

void bd(long long x)
{
	long long i,sz=al[x].size(),l;
	vector<long long> v;
	
	vtd[x]=1;
	for(i=0;i<sz;i++)
	{
		l=al[x][i];
		if(!vtd[l])
		{
			pr[l]=x;
			dh[l]=dh[x]+1;
			bd(l);
			v.push_back(l);
		}
	}
	al[x]=v;
}

void dfs(long long x)
{
	long long i,j,sz=al[x].size(),k,l,w,p[2],e,mk,mk2;
	
	for(i=0;i<=nn;i++)
	{
		dp[x][i]=-inf;
	}
	for(i=0;i<sz;i++)
	{
		l=al[x][i];
		dfs(l);
	}
	for(mk=0;mk<1ll<<sz;mk++)
	{
		dp2[mk]=0;
		for(i=0;i<sz;i++)
		{
			l=al[x][i];
			dp2[mk]+=dp[l][0]*(mk>>i&1);
		}
	}
	for(i=1;i<=nn;i++)
	{
		if(spc[x][i])
		{
			e=0;
			for(j=0;j<sz;j++)
			{
				l=al[x][j];
				if(spc[l][i])
				{
					p[e]=j;
					e++;
				}
			}
			if(e)
			{
				k=al[x][p[0]];
			}
			if(e==2)
			{
				l=al[x][p[1]];
			}
			if(e==2||(e==1&&!spc[pr[x]][i]))
			{
				if(e==2)
				{
					w=dp[k][i]+dp[l][i];
					mk=1ll<<p[0]|1ll<<p[1];
				}
				else
				{
					w=dp[k][i]+wg[i]*(x==ed[i].fr);
					mk=1ll<<p[0];
				}
				for(mk2=0;mk2<1ll<<sz;mk2++)
				{
					if(!(mk2&mk))
					{
						dp2[mk2|mk]=max(dp2[mk2|mk],dp2[mk2]+w);
					}
				}
			}
		}
	}
	dp[x][0]=dp2[(1ll<<sz)-1];
	for(i=1;i<=nn;i++)
	{
		if(spc[x][i])
		{
			e=0;
			for(j=0;j<sz;j++)
			{
				l=al[x][j];
				if(spc[l][i])
				{
					p[e]=j;
					e++;
				}
			}
			if(e)
			{
				k=al[x][p[0]];
			}
			if(e==1&&spc[pr[x]][i])
			{
				dp[x][i]=dp2[(1ll<<sz)-1^1ll<<p[0]]+dp[k][i];
			}
			else if(!e)
			{
				dp[x][i]=dp[x][0]+wg[i]*(x==ed[i].fr);
			}
		}
	}
	
}

int main()
{
	long long i,j,ii,k,l,w;
	
	scanf("%lld%lld",&n,&m);
	for(i=0;i<m;i++)
	{
		scanf("%lld%lld%lld",&k,&l,&w);
		ttl+=w;
		if(!w)
		{
			al[k].push_back(l);
			al[l].push_back(k);
		}
		else
		{
			nn++;
			ed[nn]={k,l};
			wg[nn]=w;
		}
	}
	bd(1);
	for(i=1;i<=nn;i++)
	{
		k=ed[i].fr;
		l=ed[i].sc;
		nm=0;
		for(ii=0;ii<2;ii++)
		{
			for(;dh[k]>dh[l];k=pr[k])
			{
				nm++;
				ca[nm]=k;
			}
			swap(k,l);
		}
		for(;k!=l;k=pr[k],l=pr[l])
		{
			nm++;
			ca[nm]=k;
			nm++;
			ca[nm]=l;
		}
		nm++;
		ca[nm]=k;
		if(nm%2)
		{
			for(j=1;j<=nm;j++)
			{
				spc[ca[j]][i]=1;
			}
		}
	}
	dfs(1);
	printf("%lld\n",ttl-dp[1][0]);
}

Compilation message (stderr)

training.cpp: In function 'void dfs(long long int)':
training.cpp:123:27: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
  123 |     dp[x][i]=dp2[(1ll<<sz)-1^1ll<<p[0]]+dp[k][i];
      |                  ~~~~~~~~~^~
training.cpp: In function 'int main()':
training.cpp:138:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |  scanf("%lld%lld",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
training.cpp:141:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |   scanf("%lld%lld%lld",&k,&l,&w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• 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