oj.uz

Submission #986309

# Submission time Handle Problem Language Result Execution time Memory
986309 2024-05-20T09:47:12 Z Pyqe Training (IOI07_training) C++17
100 / 100
 37 ms 33748 KB 
#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

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

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 33628 KB Output is correct
2 Correct 16 ms 33676 KB Output is correct

Subtask #4
7.0 / 7.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16988 KB Output is correct
2 Correct 7 ms 16984 KB Output is correct
3 Correct 8 ms 16984 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 33592 KB Output is correct
2 Correct 18 ms 33372 KB Output is correct
3 Correct 18 ms 33372 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 17100 KB Output is correct
2 Correct 8 ms 16988 KB Output is correct
3 Correct 27 ms 33616 KB Output is correct
4 Correct 10 ms 16988 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 33624 KB Output is correct
2 Correct 37 ms 33628 KB Output is correct
3 Correct 27 ms 33628 KB Output is correct
4 Correct 22 ms 33748 KB Output is correct