Submission #47919

#	Time	Username	Problem	Language	Result	Execution time	Memory
47919		cheater2k	Tug of War (BOI15_tug)	C++17	23 / 100	945 ms	11236 KiB

tug

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

const int N = 30005;
const int MAX = 600005;

int n, diff, a[N], s[N];
int par[N], nver[N], nedge[N];
vector < pair<int,int> > g[N];
int deg[N];
int sum;
bool del[N];
map <int, int> mp[N];
vector <int> cycle;

int anc(int p) { return p == par[p] ? p : par[p] = anc(par[p]); }

void add(int u, int v, int s) {
	g[u].push_back({v, s}); ++deg[u];
	g[v].push_back({u, s}); ++deg[v];
	mp[u][v] = mp[v][u] = s;
}

void find_cycle(int u) {
	del[u] = true;
	cycle.push_back(u);
	for (auto &e : g[u]) if (!del[e.first]) {
		return find_cycle(e.first);
	}
}

void dfs_tree(int u, int p) {
	if (u <= n) sum += a[u];
	for (auto &e : g[u]) {
		int v = e.first; if (v == p || deg[v] == 2) continue;
		dfs_tree(v, u);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> diff;

	for (int i = 1; i <= n + n; ++i) { // reset Disjoint Set
		par[i] = i;
		nver[i] = 1;
		nedge[i] = 0;
	}

	for (int i = 1; i <= n + n; ++i) {
		int u, v; cin >> u >> v >> s[i];
		v += n;
		int pu = anc(u), pv = anc(v);
		if (pu == pv) {
			if (nver[pu] > nedge[pu]) ++nedge[pu], add(u, v, s[i]);
			else { // invalid
				return printf("NO\n"), 0;
			}
		} else { // join u and v
			nver[pu] += nver[pv]; nver[pv] = 0;
			nedge[pu] += nedge[pv] + 1; nedge[pv] = 0;
			par[pv] = pu;
			add(u, v, s[i]);
		}
	}

	queue <int> q;
	for (int i = 1; i <= n + n; ++i) if (deg[i] == 1) q.push(i);

	while(!q.empty()) {
		int u = q.front(); q.pop();
		del[u] = true;
		for (auto &e : g[u]) {
			int v = e.first, w = e.second; 
			if (del[v]) continue;
			a[u] = w;
			if (--deg[v] == 1) q.push(v);
		}
	}

	// DP
	bitset <MAX> bs;
	bs.set(0);

	for (int i = 1; i <= n + n; ++i) if (!del[i]) { // in cycle
		cycle.clear();
		find_cycle(i);
		sum = 0;
		for (int j : cycle) {
			dfs_tree(j, j);
		}

		int sz = cycle.size();
		int sum1 = 0, sum2 = 0;

		for (int i = 0; i < sz; ++i) {
			int w = mp[cycle[i]][cycle[(i + 1) % sz]];
			if (cycle[i] <= n) sum1 += w;
			if (cycle[(i + 1) % sz] <= n) sum2 += w;
		}

		// group 1
		int c = sum + sum1; // first choice
		int d = sum + sum2; // second choice
		bs = bs | (bs << c) | (bs << d);
	}

	// check
	sum = 0;
	for (int i = 1; i <= n + n; ++i) sum += s[i];

	for (int i = 1; i <= sum; ++i) if (bs[i]) {
		int j = sum - i; // group 2
		if (abs(i - j) <= diff) {
			return printf("YES\n"), 0;		
		}
	}

	printf("NO\n");
}

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