Submission #162070

#	Time	Username	Problem	Language	Result	Execution time	Memory
162070		amoo_safar	Tug of War (BOI15_tug)	C++14	100 / 100	1176 ms	8284 KiB

tug

#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1e9 + 7;
const int Maxn = 3e4 + 10;
const ll Inf = 1000000000000000LL;

ll s[Maxn << 1], deg[Maxn << 1];

vector<pll> G[Maxn << 1];

queue<ll> q;

ll mk[Maxn << 1];
ll sm = 0, t = 1;
void DFS(ll u){
	sm += 2;
	sm -= G[u].size();
	mk[u] = t;
	for(auto adj : G[u]){
		if(mk[adj.F] == 0) DFS(adj.F);
	}
}
ll del[Maxn << 1];


vector<ll> V;
void DFS2(ll u, ll p, ll p2){
	mk[u] = 1;
	for(auto e : G[u]){
		if(del[e.F]) continue;
		if(e.F == p || e.F == p2) continue;
		V.pb(s[e.S]);
		if(!mk[e.F]) DFS2(e.F, u, p2);
	}
}


bitset<600010> bt;

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll n, k;
	cin >> n >> k;
	ll l, r;
	for(int i = 0; i < n + n; i++){
		cin >> l >> r >> s[i];
		r += n;
		G[l].pb({r, i});
		G[r].pb({l, i});
		deg[l] ++;
		deg[r] ++;
	}
	for(int i = 1; i <= n + n; i++){
		if(!mk[i]){
			DFS(i);
			t ++;
			if(sm != 0) return cout << "NO", 0;
		}
	}
	
	ll S = 0;
	
	for(int i = 1; i <= n + n; i++){
		if(deg[i] == 1) q.push(i);
	}
	while(q.size()){
		ll fr = q.front(); q.pop();
		del[fr] = 1;
		for(auto e : G[fr]){
			if(del[e.F]) continue;
			if(fr > n) S -= s[e.S];
			else S += s[e.S];
			
			deg[e.F] --;
			if(deg[e.F] == 1){
				q.push(e.F);
			}
		}
	}
	//cerr << S << '\n';
	memset(mk, 0, sizeof mk);
	bt[0] = 1;
	ll A = 0;
	for(int i = 1; i <= n + n; i++){
		if(del[i] || mk[i]) continue;
		V.clear();
		DFS2(i, 0, i);
		
		ll cnt = 0;
		for(auto x : V) cnt = x - cnt;
		//cerr << cnt << '\n';
		cnt = abs(cnt);
		bt |= (bt << cnt);
		A += cnt;
	}
	for(int i = 0; i <= 600000; i++){
		if(bt[i]){
			ll res = S + i - (A - i);
			if(abs(res) <= k) return cout << "YES\n", 0;
		}
	}
	
	cout << "NO";
	return 0;
}

/*

2 5
1 1 1
1 2 4
2 2 1
2 1 4


2 5
1 1 1
1 1 3
2 1 1
1 2 5

4 1
1 1 1
2 1 2
2 2 8
1 2 2
3 3 5
3 3 2
4 4 1
4 4 2

*/

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