oj.uz

Submission #127078

# Submission time Handle Problem Language Result Execution time Memory
127078 2019-07-08T21:18:07 Z TadijaSebez Tug of War (BOI15_tug) C++11
0 / 100
 957 ms 3340 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 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));*/
	bitset<N*20> dp;
	dp[N*10+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(N*10-i);
		ans=min(ans,x);
	}
	if(ans<=k) printf("YES\n");
	else printf("NO\n");
	return 0;
}

Compilation message

tug.cpp: In function 'int main()':
tug.cpp:12: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:15: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 7 ms 2424 KB Output is correct
2 Incorrect 7 ms 2424 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2424 KB Output is correct
2 Incorrect 7 ms 2424 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

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

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2424 KB Output is correct
2 Incorrect 7 ms 2424 KB Output isn't correct
3 Halted 0 ms 0 KB -