#include<bits/stdc++.h>
#define doi(i) if(!adj[i].size()) {cout << "NO\n";return 0;}if(adj[i].size()<2) {q.push(i);sum+=(i>n/2?1:-1)*((*begin(adj[i])).second);}
#define shift(x) ((x)>0?bt<<(x):bt>>(-x))
using namespace std;
multiset<pair<int, int>> adj[200100];
queue<int> q;
bool del[200100];
bitset<1200000> bt;
int tot;
void dfs(int n, int N) {
if (del[n]) return;
del[n] = true;
int nxt, cost;
tie(nxt, cost) = *adj[n].begin();
if(nxt>N)
tot += cost;
else
tot-=cost;
if (!del[nxt]) {
adj[nxt].erase({n, cost});
adj[n].clear();
dfs(nxt, N);
}
}
int main() {
cin.sync_with_stdoi(false);
cin.tie(nullptr);
int n, k, sum = 0;
cin >> n >> k;
n*=2;
for(int i = 1; i <= n; i++) {
int x, y, w;
cin >> x >> y >> w;
y+=n/2;
adj[x].insert({y,w});
adj[y].insert({x,w});
}
for(int i = 1; i <= n; i++) {
doi(i);
}
while(q.size()) {
int x = q.front(), i = (*adj[x].begin()).first, w= (*adj[x].begin()).second;
del[x] = 1;
q.pop();
adj[i].erase({x,w});
doi(i);
}
bt[sum+600000]=1;
bt[sum-600000]=1;
for(int i = 1; i <= n; i++) {
if(!del[i]) {
tot = 0;
adj[i].erase(adj[i].begin());
dfs(i, n/2);
bt = shift(tot)|shift(-tot);
}
}
for(int i = -k; i <= k; i++) {
if(bt[600000+i]) {
cout << "YES\n";
return 0;
}
}
cout << "NO\n";
}
Compilation message
tug.cpp: In function 'void dfs(int, int)':
tug.cpp:17:5: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
17 | else
| ^~~~
tug.cpp:19:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
19 | if (!del[nxt]) {
| ^~
tug.cpp: In function 'int main()':
tug.cpp:26:9: error: 'std::istream' {aka 'class std::basic_istream<char>'} has no member named 'sync_with_stdoi'; did you mean 'sync_with_stdio'?
26 | cin.sync_with_stdoi(false);
| ^~~~~~~~~~~~~~~
| sync_with_stdio
