Submission #667185

#	Time	Username	Problem	Language	Result	Execution time	Memory
667185		Kahou	Tug of War (BOI15_tug)	C++14	100 / 100	93 ms	8212 KiB

tug

// radal lanat bet.

#include<bits/stdc++.h>
using namespace std;
#define F first
#define s second
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;

const int N = 6e4 + 5;
int n, k, s[N], bk[N], to[N], from[N], t, dp[N], w[N][2], cnt[20*N], X;
int vis[N], mark[N];
int CC[N];
int sum;
vector<int> adj[N];
vector<int> vc[N];
vector<int> pth;

bitset<20*N> bs;

void dfs(int u, int p) {
	vis[u] = 1;
	CC[u] = t;
	for (int id:adj[u]) {
		if (id == p) continue;
		int v = to[id]^from[id]^u;
		if (!vis[v]) {
			pth.push_back(id);
			dfs(v, id);
			pth.pop_back();
		}
		else if (vis[v] == 1) {
			bk[t]++;
			if (!vc[t].empty()) continue;
			int pt = pth.size()-1;
			mark[from[id]] = mark[to[id]] = 1;
			vc[t].push_back(id);
			while (pt > 0 && from[pth[pt]] != v && to[pth[pt]] != v) {
				mark[from[pth[pt]]] = mark[to[pth[pt]]] = 1;
				vc[t].push_back(pth[pt--]);
			}
			mark[from[pth[pt]]] = mark[to[pth[pt]]] = 1;
			vc[t].push_back(pth[pt]);
		}
	}
	vis[u] = 2;
}

void dfs2(int u, int p) {
	for (int id:adj[u]) {
		int v = from[id]^to[id]^u;
		if (v == p || mark[v]) continue;
		dfs2(v, u);
		dp[u] += dp[v];
		if (u <= n) dp[u] += s[id];
	}
}

void solve() {
	cin >> n >> k;
	for (int i = 1; i <= 2*n; i++) {
		int l, r;
		cin >> l >> r >> s[i];
		r += n;
		adj[l].push_back(i);
		adj[r].push_back(i);
		from[i] = l;
		to[i] = r;
		sum += s[i];
	}
	
	for (int u = 1; u <= 2*n; u++) {
		if (!vis[u]) {
			t++;
			dfs(u, 0);
			if (bk[t] > 1) {
				cout << "NO" << endl;
				return;
			}
		}
	}
	for (int u = 1; u <= 2*n; u++) {
		if (mark[u]) {
			dfs2(u, 0);
			w[CC[u]][0] += dp[u];
			w[CC[u]][1] += dp[u];
		}
	}
	for (int x = 1; x <= t; x++) {
		for (int i = 0; i < (int)vc[x].size(); i++) {
			int id = vc[x][i];
			w[x][i&1] += s[id];
		}
	}

	for (int x = 1; x <= t; x++) {
		if (w[x][0] > w[x][1]) swap(w[x][0], w[x][1]);
		X += w[x][0];
		cnt[w[x][1]-w[x][0]]++;
	}

	if (X > (sum+k)/2) {
		cout << "NO" << endl;
		return;
	}
	if (X >= (sum-k+1)/2) {
		cout << "YES" << endl;
		return;
	}
	
	for (int x = 1; x < 20*N; x++) {
		while (cnt[x] >= 3) {
			cnt[x] -= 2;
			cnt[x<<1]++;
		}
	}
	bs[0] = 1;
	for (int x = 1; x < 20*N; x++) {
		for (int i = 1; i <= cnt[x]; i++) {
			bs = (bs<<x*i)|bs;
		}
	}

	int iy = bs._Find_next((sum-k+1)/2-X-1);
	cout << (iy <= (sum+k)/2-X ? "YES":"NO") << endl;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	solve();
	return 0;
}

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