#undef _GLIBCXX_DEBUG
#pragma GCC optimize("Ofast,inline")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("bmi,bmi2,lzcnt,popcnt")
#pragma GCC target("movbe")
#pragma GCC target("aes,pclmul,rdrnd")
#pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2")
#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;
inline int read() {
int v = 0;
int sign = 1;
char c = getchar();
if (c == '-') {
sign = -1;
} else {
v += c - '0';
}
while ((c = getchar()) != EOF && c != ' ' && c != '\n') {
v *= 10; v += c - '0';
}
return v * sign;
}
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(adj[nxt].find({n, cost}));
adj[n].clear();
dfs(nxt, N);
}
}
int main() {
int n(read()), k(read()), sum = 0;
n*=2;
for(int i = 1; i <= n; i++) {
int x,(read()), y(read()), w(read());
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(adj[i].find({x,w}));
doi(i);
}
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:38:5: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
38 | else
| ^~~~
tug.cpp:40:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
40 | if (!del[nxt]) {
| ^~
tug.cpp: In function 'int main()':
tug.cpp:50:15: warning: unnecessary parentheses in declaration of 'read' [-Wparentheses]
50 | int x,(read()), y(read()), w(read());
| ^
tug.cpp:50:13: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
50 | int x,(read()), y(read()), w(read());
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
10068 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
10068 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
10068 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
10068 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
11976 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
10068 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
10068 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
