Submission #677215

#	Time	Username	Problem	Language	Result	Execution time	Memory
677215		ajab_01	Tug of War (BOI15_tug)	C++17	41 / 100	2516 ms	4388 KiB

tug

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
vector<int> g[N];
int l[N] , r[N] , p[N] , cnt[2] , n , k;
bool mark[N] , ch , flg = 1;

void dfs(int ver , int sit){
	mark[ver] = 1;
	cnt[sit]++;
	for(int i : g[ver]){
		if(mark[i]) continue;
		dfs(i , sit ^ 1);
	}
}

bool check(int mask){
	bool vis[N];
	memset(vis , 0 , sizeof(vis));
	int sum1 = 0 , sum2 = 0;
	for(int i = 0 ; i < 2 * n ; i++){
		if(mask & (1 << i)){
			if(vis[r[i]])
				return 0;
			vis[r[i]] = 1;
			sum1 += p[i];
		}
		else{
			if(vis[l[i]])
				return 0;
			vis[l[i]] = 1;
			sum2 += p[i];
		}
	}

	return abs(sum1 - sum2) <= k;
}

int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> k;
	if(n <= 10){
		for(int i = 0 ; i < 2 * n ; i++){
			cin >> l[i] >> r[i] >> p[i];
			r[i] += n;
		}

		for(int mask = 0 ; mask < (1 << 2 * n) ; mask++)
			if(check(mask))
				ch = 1;

		if(ch)
			cout << "YES" << '\n';
		else
			cout << "NO" << '\n';
		return 0;
	}

	for(int i = 1 ; i <= 2 * n ; i++){
		cin >> l[i] >> r[i] >> p[i];
		g[i].push_back(l[i] + 2 * n);
		g[l[i] + 2 * n].push_back(i);
		g[i].push_back(r[i] + 3 * n);
		g[r[i] + 3 * n].push_back(i);
	}

	for(int i = 1 ; i <= 4 * n ; i++){
		if(!mark[i]){
			cnt[0] = cnt[1] = 0;
			dfs(i , (i > 2 * n ? 1 : 0));
			if(cnt[0] != cnt[1]) flg = 0;
		}
	}

	if(flg)
		cout << "YES" << '\n';
	else
		cout << "NO" << '\n';
	return 0;
}

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