#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;
typedef long long ll;
const int N = 30333;
int n, k;
int l[2 * N];
int r[2 * N];
int s[2 * N];
vector<int> g[4 * N];
int ver;
int pos;
bool was[4 * N];
ll sum[2];
vector<int> comp;
bool have[4 * N];
bool taken[4 * N];
bitset<40 * N + 1> dp;
void addEdge(int v, int u) {
g[v].push_back(u);
g[u].push_back(v);
}
void dfs(int v) {
if (v < 2 * n) {
sum[ver & 1] += s[v];
ver++;
} else pos++;
was[v] = true;
comp.push_back(v);
for (int u : g[v])
if (!was[u])
dfs(u);
}
bool OK;
void Go(int p) {
taken[p] = true;
for (int x : g[p]) {
if (!have[x]) {
assert((p == 2 * n + l[x]) || (p == (3 * n + r[x])));
int w = (p ^ (2 * n + l[x]) ^ (3 * n + r[x]));
if (taken[w])
OK = false;
else {
sum[(w < 3 * n)] += s[x];
taken[w] = true;
have[x] = true;
Go(w);
}
}
}
}
bool Try(int i, int p) {
OK = true;
for (int it : comp) {
have[it] = false;
taken[it] = false;
}
sum[0] = 0;
sum[1] = 0;
sum[(p < 3 * n)] += s[i];
have[i] = true;
Go(p);
return OK;
}
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
scanf("%d%d", &n, &k);
assert(k >= 0);
for (int i = 0; i < 2 * n; i++) {
scanf("%d%d%d", &l[i], &r[i], &s[i]);
--l[i];--r[i];
addEdge(i, 2 * n + l[i]);
addEdge(i, 3 * n + r[i]);
}
vector<pair<int, int>> canSame;
vector<int> mustDiff;
for (int i = 0; i < 2 * n; i++) if (!was[i]) {
ver = 0;
pos = 0;
sum[0] = 0;
sum[1] = 0;
comp.clear();
dfs(i);
if (ver > pos) {
printf("NO\n");
return 0;
}
assert(Try(i, 3 * n + r[i]) || Try(i, 2 * n + l[i]));
if (!Try(i, 3 * n + r[i])) {
assert(Try(i, 2 * n + l[i]));
mustDiff.push_back(sum[0] - sum[1]);
} else if (!Try(i, 2 * n + l[i])) {
assert(Try(i, 3 * n + r[i]));
mustDiff.push_back(sum[0] - sum[1]);
} else {
assert(Try(i, 2 * n + l[i]));
int S00 = sum[0];
int S01 = sum[1];
assert(Try(i, 3 * n + r[i]));
int S10 = sum[0];
int S11 = sum[1];
assert(abs(S00 - S01) <= 1);
assert(abs(S10 - S11) <= 1);
canSame.push_back({S00 - S01, S10 - S11});
}
}
dp[20 * N] = 1;
for (auto x : canSame) {
int a = x.first;
int b = x.second;
if (a >= 0 && b >= 0) {
dp = ((dp << a) | (dp << b));
} else if (a < 0 && b >= 0) {
dp = ((dp >> (-a)) | (dp << b));
} else if (a >= 0 && b < 0) {
dp = ((dp << a) | (dp >> (-b)));
} else {
dp = ((dp >> (-a)) | (dp >> (-b)));
}
}
for (int x : mustDiff) {
if (x < 0)
dp = (dp >> (-x));
else
dp = (dp << x);
}
bool ok = false;
for (int i = 0; i <= k; i++)
if (dp[20 * N + i] || dp[20 * N - i])
ok = true;
if (ok)
printf("YES\n");
else
printf("NO\n");
return 0;
}
Compilation message
tug.cpp: In function 'int main()':
tug.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
95 | scanf("%d%d", &n, &k);
| ~~~~~^~~~~~~~~~~~~~~~
tug.cpp:98:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
98 | scanf("%d%d%d", &l[i], &r[i], &s[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
7124 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
7124 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
449 ms |
5708 KB |
Output is correct |
| 2 |
Correct |
12 ms |
5204 KB |
Output is correct |
| 3 |
Correct |
378 ms |
5704 KB |
Output is correct |
| 4 |
Correct |
11 ms |
5076 KB |
Output is correct |
| 5 |
Correct |
383 ms |
5700 KB |
Output is correct |
| 6 |
Correct |
11 ms |
5076 KB |
Output is correct |
| 7 |
Correct |
426 ms |
5720 KB |
Output is correct |
| 8 |
Correct |
10 ms |
5076 KB |
Output is correct |
| 9 |
Correct |
399 ms |
5716 KB |
Output is correct |
| 10 |
Correct |
15 ms |
5076 KB |
Output is correct |
| 11 |
Correct |
413 ms |
5708 KB |
Output is correct |
| 12 |
Correct |
10 ms |
5076 KB |
Output is correct |
| 13 |
Correct |
455 ms |
5704 KB |
Output is correct |
| 14 |
Correct |
366 ms |
5716 KB |
Output is correct |
| 15 |
Correct |
11 ms |
5076 KB |
Output is correct |
| 16 |
Correct |
419 ms |
5708 KB |
Output is correct |
| 17 |
Correct |
10 ms |
5076 KB |
Output is correct |
| 18 |
Correct |
361 ms |
5804 KB |
Output is correct |
| 19 |
Correct |
10 ms |
5076 KB |
Output is correct |
| 20 |
Correct |
429 ms |
5716 KB |
Output is correct |
| 21 |
Correct |
12 ms |
5588 KB |
Output is correct |
| 22 |
Runtime error |
16 ms |
10404 KB |
Execution killed with signal 6 |
| 23 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
7124 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
