oj.uz

Submission #127072

# Submission time Handle Problem Language Result Execution time Memory
127072 2019-07-08T21:03:07 Z TadijaSebez Tug of War (BOI15_tug) C++11
0 / 100
 3000 ms 3312 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;
			for(auto e:E[x]) if(deg[e.first]==2 && e.first!=par)
			{
				y=e.first;
				w=e.second;
			}
			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));
	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);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~
tug.cpp:56:10: warning: 'w' may be used uninitialized in this function [-Wmaybe-uninitialized]
    all+=t*w;
         ~^~
tug.cpp:59:4: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
    if(x==i) break;
    ^~

Subtask #1
0 / 18.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3032 ms 3312 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

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