oj.uz

Submission #127481

# Submission time Handle Problem Language Result Execution time Memory
127481 2019-07-09T12:28:12 Z TadijaSebez Tug of War (BOI15_tug) C++11
0 / 100
 74 ms 13432 KB 
#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);
	}
	/*set<int> dp;
	dp.insert(sum[1]-sum[0]);
	for(int x:cyc)
	{
		vector<int> ins;
		for(int y:dp)
		{
			ins.pb(y+x);
			ins.pb(y-x);
		}
		dp.clear();
		for(int y:ins) dp.insert(y);
	}
	int ans=1e9;
	for(int y:dp) ans=min(ans,abs(y));*/
	/*const int lim=N*10;
	bitset<lim> dp;
	dp[lim/2+sum[1]-sum[0]]=1;
	for(int x:cyc)
	{
		x=abs(x);
		dp=(dp>>x)|(dp<<x);
	}
	int ans=1e9;
	for(int i=0;i<N*20;i++) if(dp[i])
	{
		int x=abs(lim/2-i);
		ans=min(ans,x);
	}*/
	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>=0?sum_dp[k-cyc[i]*cnt]-dp[k-cyc[i]*cnt]:0);
			if(k-cyc[i]*cnt>=0) tmp-=sum_dp[k-cyc[i]*cnt]-dp[k-cyc[i]*cnt];
			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));
	//printf("%i\n",ans);
	if(ans<=k) printf("YES\n");
	else printf("NO\n");
	return 0;
}

Compilation message

tug.cpp: In function 'int main()':
tug.cpp:106:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0,j=0;i<cyc.size();i=j)
                  ~^~~~~~~~~~~
tug.cpp:109: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.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 12280 KB Output is correct
2 Correct 74 ms 12280 KB Output is correct
3 Incorrect 69 ms 12420 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 12280 KB Output is correct
2 Correct 74 ms 12280 KB Output is correct
3 Incorrect 69 ms 12420 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 13432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 12280 KB Output is correct
2 Correct 74 ms 12280 KB Output is correct
3 Incorrect 69 ms 12420 KB Output isn't correct
4 Halted 0 ms 0 KB -