Submission #351990

#	Time	Username	Problem	Language	Result	Execution time	Memory
351990		minoum	Tug of War (BOI15_tug)	C++17	100 / 100	1364 ms	8812 KiB

tug

#include<bits/stdc++.h>

using namespace std;
typedef long long int ll;

const int MAXN = 6e4;
int n, k, s[MAXN], l[MAXN], r[MAXN], ss = 0, s1 = 0, dd[MAXN], ww[2];
vector <int> adj[MAXN]; //id,u
bool deadh[MAXN], deadt[MAXN];

inline bool ch(){
	set <pair<int,int>> deg;
	for(int i = 0; i < 2*n; i++){
		dd[i] = (int)adj[i].size();
		deg.insert({dd[i], i});
	}
	while(!deg.empty()){
		if(deg.begin()->first > 1) break;
		if(deg.begin()->first <= 0) return false;
		int t = deg.begin()->second, h = -1, v2; deg.erase(*deg.begin());
		for(auto i: adj[t])
			if(!deadh[i]){
				h = i; v2 = ((t<n)?r[h]:l[h]); break;
			}
		s1 += (t<n?s[h]:0);
		deadt[t] = true; deadh[h] = true;
		v2 = (t<n?r[h]:l[h]);
		if(!deadt[v2]){
			deg.erase({dd[v2],v2});
			dd[v2]--;
			deg.insert({dd[v2], v2});
		}
	}
	return true;
}

inline void dfs(int v){
	int hh = 0, v2;
	while(!deadt[v]){
		for(auto i: adj[v])
			if(!deadh[i]){
				int h = i;
				ww[hh] += s[h]; deadh[h] = true; deadt[v] = true;
				v2 = ((v<n)?r[h]:l[h]);
				break;
			}
		hh = 1-hh; v = v2;
	}
	return;
}

int main()
{
//	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//	cin >> n >> k;
	scanf("%d",&n); scanf("%d", &k);
	for(int i = 0; i < 2*n; i++){
		//cin >> l[i] >> r[i] >> s[i]; 
		scanf("%d", l+i); scanf("%d", r+i); scanf("%d", s+i);
		l[i]--; r[i]--; r[i] += n; ss += s[i];
		adj[l[i]].push_back(i);
		adj[r[i]].push_back(i);
	}
//	int b = (ss-k+1)/2, e = (ss+k)/2; b = max(b, 0);
	bool check = ch();
	if(!check){
//		cout << "NO" << '\n';
		printf("NO");
		return 0;
	}
	if(ss-(2*s1) <= k && -ss+(2*s1) <= k){
			//cout << "YES" << '\n';
			printf("YES");
			return 0;
		}
	vector <pair<int,int>> w;
	for(int i = 0; i < 2*n; i++)
		if(!deadt[i]){
			ww[0] = ww[1] = 0;
			dfs(i);
			w.push_back({ww[0],ww[1]});
		}  
	bitset <MAXN*10> bt;
	bt[s1] = 1;
	for(auto i: w)
		bt = (bt<<i.first) | (bt<<i.second);
	for(int i = 0; i < ss; i++)
		if(bt[i] && ss-(2*i) <= k && -ss+(2*i) <= k){
			//cout << "YES" << '\n';
			printf("YES");
			return 0;
		}
//	cout << "NO" << '\n';
	printf("NO");
	return 0; 
}

Compilation message (stderr)

tug.cpp: In function 'int main()':
tug.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   56 |  scanf("%d",&n); scanf("%d", &k);
      |  ~~~~~^~~~~~~~~
tug.cpp:56:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   56 |  scanf("%d",&n); scanf("%d", &k);
      |                  ~~~~~^~~~~~~~~~
tug.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |   scanf("%d", l+i); scanf("%d", r+i); scanf("%d", s+i);
      |   ~~~~~^~~~~~~~~~~
tug.cpp:59:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |   scanf("%d", l+i); scanf("%d", r+i); scanf("%d", s+i);
      |                     ~~~~~^~~~~~~~~~~
tug.cpp:59:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |   scanf("%d", l+i); scanf("%d", r+i); scanf("%d", s+i);
      |                                       ~~~~~^~~~~~~~~~~
tug.cpp:39:16: warning: 'v2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   39 |  while(!deadt[v]){
      |         ~~~~~~~^
tug.cpp:38:14: note: 'v2' was declared here
   38 |  int hh = 0, v2;
      |              ^~

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