Submission #127388

#	Time	Username	Problem	Language	Result	Execution time	Memory
127388		TadijaSebez	Tug of War (BOI15_tug)	C++11	0 / 100	73 ms	13304 KiB

tug

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=60050;
vector<pair<int,int>> E[N];
bool was[N];
int n,k;
int sum[2],deg[N];
int sum_dp[N*20],go[N*20];
bool dp[N*20];
int main()
{
	int u,v,w;
	scanf("%i %i",&n,&k);
	for(int i=1;i<=2*n;i++)
	{
		scanf("%i %i %i",&u,&v,&w);
		v+=n;
		E[u].pb({v,w});
		E[v].pb({u,w});
		deg[u]++;
		deg[v]++;
	}
	queue<int> q;
	for(int i=1;i<=2*n;i++) if(deg[i]==1) q.push(i),was[i]=1;
	while(q.size())
	{
		int x=q.front();
		q.pop();
		int b=x>n;
		bool ok=0;
		for(auto e:E[x]) if(!was[e.first])
		{
			ok=1;
			v=e.first;
			w=e.second;
		}
		if(!ok || deg[v]==1) return 0*printf("NO\n");
        sum[b]+=w;
        deg[v]--;
		if(deg[v]==1) was[v]=1,q.push(v);
	}
	for(int i=1;i<=2*n;i++) if(!was[i] && deg[i]!=2) return 0*printf("NO\n");
	vector<int> cyc;
	for(int i=1;i<=2*n;i++) if(!was[i])
	{
		int all=0;
		int par=0;
		for(int x=i,t=1,y;;t=-t)
		{
			int w;
			was[x]=1;
			bool ok=0;
			for(auto e:E[x]) if(deg[e.first]==2 && e.first!=par)
			{
				y=e.first;
				w=e.second;
				ok=1;
			}
			if(!ok)
			{
				vector<int> ws;
				for(auto e:E[i]) if(deg[e.first]==2) ws.pb(e.second);
				all=ws[0]-ws[1];
				break;
			}
			all+=t*w;
			par=x;
			x=y;
			if(x==i) break;
		}
		cyc.pb(all);
	}
	dp[N*10+sum[1]-sum[0]]=1;
	for(int &x:cyc) x=abs(x);
	sort(cyc.begin(),cyc.end());
	for(int i=0,j=0;i<cyc.size();i=j)
	{
		int cnt=0;
		for(j=i;j<cyc.size() && cyc[i]==cyc[j];j++) cnt++;
		for(int k=0;k<N*20;k++) sum_dp[k]=dp[k]+(k>=cyc[i]*2?sum_dp[k-cyc[i]*2]:0);
		for(int k=0;k<N*20;k++)
		{
			if(k<cyc[i]*2) go[k]=k+cyc[i]*cnt;
			else
			{
				go[k]=go[k-cyc[i]*2];
				if(go[k]+cyc[i]*2<N*20) go[k]+=cyc[i]*2;
			}
			int tmp=sum_dp[go[k]]-(k-cyc[i]*(cnt+2)>=0?sum_dp[k-cyc[i]*(cnt+2)]:0);
			if(tmp>0) dp[k]=1;
			else dp[k]=0;
		}
	}
	int ans=1e9+7;
	for(int i=0;i<N*20;i++) if(dp[i]) ans=min(ans,abs(N*10-i));
	if(ans<=k) printf("YES\n");
	else printf("NO\n");
	return 0;
}

Compilation message (stderr)

tug.cpp: In function 'int main()':
tug.cpp:77:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0,j=0;i<cyc.size();i=j)
                  ~^~~~~~~~~~~
tug.cpp:80:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=i;j<cyc.size() && cyc[i]==cyc[j];j++) cnt++;
           ~^~~~~~~~~~~
tug.cpp:14:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&k);
  ~~~~~^~~~~~~~~~~~~~~
tug.cpp:17:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i %i",&u,&v,&w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 18
• Subtask 2: 0 / 30
• Subtask 3: 0 / 23
• Subtask 4: 0 / 29