| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1291125 | LOLOLO | Tug of War (BOI15_tug) | C++17 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f first
#define s second
#define pb push_back
#define ep emplace
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define mem(f,x) memset(f , x , sizeof(f))
#define sz(x) (ll)(x).size()
#define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b))
#define mxx *max_element
#define mnn *min_element
#define cntbit(x) __builtin_popcountll(x)
#define len(x) (int)(x.length())
const int N = 1e5 + 100;
set <pair <int, int>> ed[N];
bool used[N];
int st = 0, s[N];
pair <int, int> dfs(int u, int v) {
if (used[u])
return {0, 0};
used[u] = 1;
pair <int, int> A = {0, 0};
for (auto x : ed[u]) {
if (x.s == v)
continue;
A = dfs(x.f, x.s);
A.f += s[x.s];
swap(A.f, A.s);
}
return A;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, k;
cin >> n >> k;
int S = 0;
for (int i = 1; i <= n * 2; i++) {
int l, r;
cin >> l >> r >> s[i];
ed[l].insert({r + n, i});
ed[r + n].insert({l, i});
S += s[i];
}
queue <int> pq;
int V1 = 0, V2 = 0;
int sz = n * 2;
for (int i = 1; i <= sz; i++) {
if (sz(ed[i]) == 0) {
cout << "NO\n";
return 0;
}
if (sz(ed[i]) == 1)
pq.push(i);
}
int L = 0;
while (sz(pq)) {
int t = pq.front();
pq.pop();
if (sz(ed[t]) == 0) {
continue;
}
auto it = *ed[t].begin();
int nxt = it.f, cost = it.s;
pair <int, int> pat = {t, cost};
ed[nxt].erase(pat);
ed[t].clear();
if (t <= n) {
L += s[cost];
V1++;
} else {
V2++;
}
if (sz(ed[nxt]) == 1) {
pq.push(nxt);
}
}
assert(v1 == v2);
for (int i = 1; i <= sz; i++) {
if (sz(ed[i]) > 2) {
cout << "NO\n";
return 0;
}
}
bitset <1000001> dp;
dp[0] = 1;
for (int i = 1; i <= sz; i++) {
if (sz(ed[i]) == 2 && used[i] == 0) {
auto it = *ed[i].begin();
pair <int, int> A = dfs(i, it.s);
dp = (dp << A.f) | (dp << A.s);
}
}
for (int i = 0; i <= 600000; i++) {
if (dp[i]) {
if (abs((S - (L + i)) - (L + i)) <= k) {
cout << "YES\n";
return 0;
}
}
}
cout << "NO\n";
return 0;
}