Submission #677214

#	Time	Username	Problem	Language	Result	Execution time	Memory
677214		faribourz	Tug of War (BOI15_tug)	C++14	0 / 100	30 ms	11372 KiB

tug

// Only GOD
// believe in yourself
// nemidam del be in darde donya!
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define bit(x, y) ((x >> y)&1)
#define sz(x) (int)x.size()
#define kill(x) return cout << x << '\n', void()
#define KILL(x) return cout << x << '\n', 0
#define int ll
const int N = 4e5+100;

vector<int> G[N];
int s[N];
vector<int> greedy;
bool mark[N];
vector<int> guni;
int n, k;
void DFS(int v){
	if(v <= 2*n)
		guni.pb(v), mark[v] = 1;
	for(int u : G[v]){
		if(!mark[u])
			DFS(u);
	}
}
int32_t main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> k;
	for(int i = 1; i <= 2*n; i++){
		int v, u;
		cin >> v >> u;
		G[i].pb(v+2*n);G[v+2*n].pb(i);
		G[i].pb(u+3*n);G[u+3*n].pb(i);
		cin >> s[i];
	}
	for(int i = 2*n+1; i <= 4*n; i++){
		if(sz(G[i]) > 2)
			KILL("NO");
	}
	for(int i =1; i <= 2*n; i++){
		if(!mark[i]){
			guni.clear();
			DFS(i);
			int res =0 ;
			for(int j =0 ; j < sz(guni);j++){
				if(j & 1){
					res += s[guni[j]];
				}
				else{
					res -= s[guni[j]];
				}
			}
			greedy.pb(abs(res));
		}
	}
	//for(int u : greedy)
	//	cout << u << ' ' ;
	int n = sz(greedy);
	for(int mask = 0; mask < (1<<n); mask++){
		int res =0 ;
		for(int i = 0; i < n; i++){
			if(bit(mask, i)){
				res -= greedy[i];
			}
			else
				res += greedy[i];
		}
		if(abs(res)<= k)
			KILL("YES");
	}
	KILL("NO");
}

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