Submission #24493

#	Time	Username	Problem	Language	Result	Execution time	Memory
24493		Bruteforceman	Tug of War (BOI15_tug)	C++11	100 / 100	113 ms	6736 KiB

tug

#include "bits/stdc++.h"
using namespace std;
bool del[2 * 30005];
int deg[2][30005];
vector <int> g[2][30005];
 
struct data
{
	int l, r, s;
	data () {}
	data (int l, int r, int s) : l(l), r(r), s(s) {}
} a[2 * 30005];
 
struct node
{
	int i, side;
	node () {}
	node (int i, int side) : i(i), side(side) {}
};
 
bool play[2 * 30010];
bool vis[2][30010];
int sum;
 
void cycle(node n) {
	// cout << n.i << " " << n.side << endl;
	if(n.side == -1) {
		play[n.i] = true;
		if(vis[0][a[n.i].l] == false) {
			cycle(node(a[n.i].l, 0));
			sum += a[n.i].s;
		} else {
			cycle(node(a[n.i].r, 1));
			sum -= a[n.i].s;
		}
	} else {
		vis[n.side][n.i] = true;
		for(auto i : g[n.side][n.i]) {
			if(del[i] == false && play[i] == false) {
				cycle(node(i, -1));
				break;
			}
		}
	}
}
 
const int tot = 20 * 30005;
bitset <tot> dp;
 
void knapsack(vector <int> v) {
	map <int, int> f;
	vector <int> u;
	for(auto i : v) {
		f[i] += 1;
	}
	for(auto i : f) {
		int p = i.first;
		int q = i.second;
		for(int j = 0; (1 << j) <= q; j++) {
			u.push_back((1 << j) * p);
			q -= 1 << j;
		}
		if(q > 0) {
			u.push_back(q * p);
		} 
	}
	dp[0] = 1;
	for(auto i : u) {
		dp |= dp << i;
	}
}
 
int main(int argc, char const *argv[])
{
	int n, k;
	scanf("%d %d", &n, &k);
	for(int i = 1; i <= n+n; i++) {
		int l, r, s;
		scanf("%d %d %d", &l, &r, &s);
		a[i] = data(l, r, s);
		g[0][l].push_back(i);
		g[1][r].push_back(i);
		++deg[0][l];
		++deg[1][r];
	}
	queue <node> Q;
	for(int i = 1; i <= n; i++) {
		if(deg[0][i] == 1) Q.push(node(i, 0));
		if(deg[1][i] == 1) Q.push(node(i, 1));
		
		if(deg[0][i] == 0 || deg[1][i] == 0) {
			printf("NO\n");
			exit(0);
		}
	}
	int add[2];
	add[0] = add[1] = 0;
	while(!Q.empty()) {
		node p = Q.front();
		Q.pop();
		for(auto i : g[p.side][p.i]) {
			if(del[i] == false) {
				add[p.side] += a[i].s;
				del[i] = true;
				if(p.side == 0) {
					--deg[1][a[i].r];
					if(deg[1][a[i].r] == 1) {
						Q.push(node(a[i].r, 1));
					}
					if(deg[1][a[i].r] == 0) {
						printf("NO\n");
						exit(0);
					}
				} else {
					--deg[0][a[i].l];
					if(deg[0][a[i].l] == 1) {
						Q.push(node(a[i].l, 0));
					}
					if(deg[0][a[i].l] == 0) {
						printf("NO\n");
						exit(0);
					}
				}
			}
		}
	}
	vector <int> v;
	int neg = 0;
	for(int i = 1; i <= n+n; i++) {
		if(play[i] == false && del[i] == false) {
			int k1, k2;
			sum = 0;
			cycle(node(i, -1));
			k1 = sum;
			v.push_back(abs(k1));
			neg -= abs(k1);
		}
	} 
	knapsack(v);
	add[0] -= add[1];
	for(int i = 0; i < tot; i++) {
		if(dp[i] == 1) {
			int hehe = i + i + neg + add[0];
			if(abs(hehe) <= k) {
				printf("YES\n");
				exit(0);
			}
		}
	}
 	printf("NO\n");
	return 0; 
}

Compilation message (stderr)

tug.cpp: In function 'int main(int, const char**)':
tug.cpp:131:12: warning: unused variable 'k2' [-Wunused-variable]
    int k1, k2;
            ^
tug.cpp:76:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &k);
                        ^
tug.cpp:79:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &l, &r, &s);
                                ^

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