#include<bits/stdc++.h>
using namespace std;
#define debug(...) 42
#define int long long
using ll = long long;
const int maxn = 6e4 + 1;
multiset<pair<int,int>> ad[maxn];
bitset<600001> dp;
bool vis[maxn];
int tot = 0;
void dfs(int u){
vis[u] = true;
if (!ad[u].size()) return;
auto [v, w] = *ad[u].begin();
tot += w;
if (!vis[v]){
ad[v].erase(ad[v].find({u, -w}));
ad[u].clear();
dfs(v);
}
}
void solve(){
int n, k;
cin >> n >> k;
for (int i = 0; i < 2 * n; i++){
int l, r, s;
cin >> l >> r >> s;
ad[l].insert({n + r, s});
ad[n + r].insert({l, -s});
}
queue<int> q;
for (int i = 1; i <= 2 * n; i++){
if (ad[i].size() == 1) q.push(i);
if (ad[i].size() == 0){
cout << "NO\n";
return;
}
}
while(q.size()){
auto cur = q.front();
q.pop();
if (ad[cur].size() == 0){
cout << "NO\n";
return;
}
auto [v, w] = *ad[cur].begin();
tot += w;
ad[cur].clear();
ad[v].erase(ad[v].find({cur, -w}));
if (ad[v].size() == 1) q.push(v);
}
vector<int> val;
if (tot != 0) val.push_back(abs(tot));
for (int i = 1; i <= 2 * n; i++){
if (!vis[i] && ad[i].size()){
tot = 0;
ad[i].erase(ad[i].begin());
dfs(i);
if (tot) val.push_back(abs(tot));
}
}
int sum = accumulate(val.begin(), val.end(), 0ll);
dp[0] = 1;
for (auto x : val) dp |= dp << x;
for (int i = 1; i <= sum; i++){
if (dp[i] && abs(2 * i - sum) <= k){
cout << "YES\n";
return;
}
}
cout << "NO\n";
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int tt = 1;
// cin >> tt;
while (tt--){
solve();
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |