#include "bits/stdc++.h"
using namespace std;
bool del[2 * 30005];
int deg[2][30005];
vector <int> g[2][30005];
struct data
{
int l, r, s;
data () {}
data (int l, int r, int s) : l(l), r(r), s(s) {}
} a[2 * 30005];
struct node
{
int i, side;
node () {}
node (int i, int side) : i(i), side(side) {}
};
bool play[2 * 30010];
bool vis[2][30010];
int sum;
bool pl[2 * 30010];
bool vs[2][30010];
int len;
void cycle(node n) {
// cout << n.i << " " << n.side << endl;
++len;
if(n.side == -1) {
play[n.i] = true;
if(vis[0][a[n.i].l] == false) {
cycle(node(a[n.i].l, 0));
sum += a[n.i].s;
} else {
cycle(node(a[n.i].r, 1));
sum -= a[n.i].s;
}
} else {
vis[n.side][n.i] = true;
for(auto i : g[n.side][n.i]) {
if(del[i] == false && play[i] == false) {
cycle(node(i, -1));
break;
}
}
}
}
void loop(node n) {
if(n.side == -1) {
pl[n.i] = true;
if(vs[1][a[n.i].r] == false) {
loop(node(a[n.i].r, 1));
sum -= a[n.i].s;
} else {
loop(node(a[n.i].l, 0));
sum += a[n.i].s;
}
} else {
vs[n.side][n.i] = true;
for(auto i : g[n.side][n.i]) {
if(del[i] == false && pl[i] == false) {
loop(node(i, -1));
break;
}
}
}
}
const int tot = 40 * 2005;
bitset <tot> dp;
void knapsack(vector <int> v) {
dp[0] = 1;
for(auto i : v) {
dp |= dp << i;
}
}
int main(int argc, char const *argv[])
{
int n, k;
scanf("%d %d", &n, &k);
for(int i = 1; i <= n+n; i++) {
int l, r, s;
scanf("%d %d %d", &l, &r, &s);
a[i] = data(l, r, s);
g[0][l].push_back(i);
g[1][r].push_back(i);
++deg[0][l];
++deg[1][r];
}
queue <node> Q;
for(int i = 1; i <= n; i++) {
if(deg[0][i] == 1) Q.push(node(i, 0));
if(deg[1][i] == 1) Q.push(node(i, 1));
if(deg[0][i] == 0 || deg[1][i] == 0) {
printf("NO\n");
exit(0);
}
}
int add[2];
add[0] = add[1] = 0;
while(!Q.empty()) {
node p = Q.front();
Q.pop();
for(auto i : g[p.side][p.i]) {
if(del[i] == false) {
add[p.side] += a[i].s;
del[i] = true;
if(p.side == 0) {
--deg[1][a[i].r];
if(deg[1][a[i].r] == 1) {
Q.push(node(a[i].r, 1));
}
if(deg[1][a[i].r] == 0) {
printf("NO\n");
exit(0);
}
} else {
--deg[0][a[i].l];
if(deg[0][a[i].l] == 1) {
Q.push(node(a[i].l, 0));
}
if(deg[0][a[i].l] == 0) {
printf("NO\n");
exit(0);
}
}
}
}
}
vector <int> v;
int neg = 0;
for(int i = 1; i <= n+n; i++) {
if(play[i] == false) {
int k1, k2;
len = 0;
sum = 0;
cycle(node(i, -1));
k1 = sum;
assert(len % 4 == 0);
sum = 0;
loop(node(i, -1));
k2 = sum;
if(k1 < k2) swap(k1, k2);
v.push_back(k1 - k2);
neg += k2;
}
}
knapsack(v);
add[0] -= add[1];
for(int i = 0; i < tot; i++) {
if(dp[i] == 1) {
int hehe = i + neg + add[0];
if(abs(hehe) <= k) {
printf("YES\n");
exit(0);
}
}
}
printf("NO\n");
return 0;
}
Compilation message
tug.cpp: In function 'int main(int, const char**)':
tug.cpp:87:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &k);
^
tug.cpp:90:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &l, &r, &s);
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
4668 KB |
Output is correct |
2 |
Correct |
0 ms |
4668 KB |
Output is correct |
3 |
Correct |
0 ms |
4668 KB |
Output is correct |
4 |
Correct |
0 ms |
4668 KB |
Output is correct |
5 |
Correct |
0 ms |
4668 KB |
Output is correct |
6 |
Correct |
0 ms |
4668 KB |
Output is correct |
7 |
Correct |
0 ms |
4668 KB |
Output is correct |
8 |
Correct |
0 ms |
4668 KB |
Output is correct |
9 |
Correct |
0 ms |
4668 KB |
Output is correct |
10 |
Correct |
0 ms |
4668 KB |
Output is correct |
11 |
Correct |
0 ms |
4668 KB |
Output is correct |
12 |
Correct |
0 ms |
4668 KB |
Output is correct |
13 |
Correct |
0 ms |
4668 KB |
Output is correct |
14 |
Correct |
0 ms |
4668 KB |
Output is correct |
15 |
Correct |
0 ms |
4668 KB |
Output is correct |
16 |
Correct |
0 ms |
4668 KB |
Output is correct |
17 |
Correct |
0 ms |
4668 KB |
Output is correct |
18 |
Correct |
0 ms |
4668 KB |
Output is correct |
19 |
Correct |
0 ms |
4668 KB |
Output is correct |
20 |
Correct |
0 ms |
4668 KB |
Output is correct |
21 |
Correct |
0 ms |
4668 KB |
Output is correct |
22 |
Runtime error |
0 ms |
4672 KB |
Execution killed because of forbidden syscall gettid (186) |
23 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
4668 KB |
Output is correct |
2 |
Correct |
0 ms |
4668 KB |
Output is correct |
3 |
Correct |
0 ms |
4668 KB |
Output is correct |
4 |
Correct |
0 ms |
4668 KB |
Output is correct |
5 |
Correct |
0 ms |
4668 KB |
Output is correct |
6 |
Correct |
0 ms |
4668 KB |
Output is correct |
7 |
Correct |
0 ms |
4668 KB |
Output is correct |
8 |
Correct |
0 ms |
4668 KB |
Output is correct |
9 |
Correct |
0 ms |
4668 KB |
Output is correct |
10 |
Correct |
0 ms |
4668 KB |
Output is correct |
11 |
Correct |
0 ms |
4668 KB |
Output is correct |
12 |
Correct |
0 ms |
4668 KB |
Output is correct |
13 |
Correct |
0 ms |
4668 KB |
Output is correct |
14 |
Correct |
0 ms |
4668 KB |
Output is correct |
15 |
Correct |
0 ms |
4668 KB |
Output is correct |
16 |
Correct |
0 ms |
4668 KB |
Output is correct |
17 |
Correct |
0 ms |
4668 KB |
Output is correct |
18 |
Correct |
0 ms |
4668 KB |
Output is correct |
19 |
Correct |
0 ms |
4668 KB |
Output is correct |
20 |
Correct |
0 ms |
4668 KB |
Output is correct |
21 |
Correct |
0 ms |
4668 KB |
Output is correct |
22 |
Runtime error |
0 ms |
4672 KB |
Execution killed because of forbidden syscall gettid (186) |
23 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
5496 KB |
Output is correct |
2 |
Correct |
9 ms |
5328 KB |
Output is correct |
3 |
Correct |
23 ms |
5496 KB |
Output is correct |
4 |
Correct |
9 ms |
5328 KB |
Output is correct |
5 |
Correct |
16 ms |
5496 KB |
Output is correct |
6 |
Correct |
0 ms |
5328 KB |
Output is correct |
7 |
Correct |
43 ms |
5496 KB |
Output is correct |
8 |
Correct |
9 ms |
5328 KB |
Output is correct |
9 |
Correct |
16 ms |
5496 KB |
Output is correct |
10 |
Correct |
9 ms |
5328 KB |
Output is correct |
11 |
Correct |
19 ms |
5496 KB |
Output is correct |
12 |
Correct |
3 ms |
5328 KB |
Output is correct |
13 |
Correct |
19 ms |
5496 KB |
Output is correct |
14 |
Correct |
36 ms |
5496 KB |
Output is correct |
15 |
Correct |
6 ms |
5328 KB |
Output is correct |
16 |
Correct |
46 ms |
5496 KB |
Output is correct |
17 |
Correct |
16 ms |
5328 KB |
Output is correct |
18 |
Correct |
36 ms |
5496 KB |
Output is correct |
19 |
Correct |
6 ms |
5328 KB |
Output is correct |
20 |
Correct |
29 ms |
5496 KB |
Output is correct |
21 |
Correct |
13 ms |
5196 KB |
Output is correct |
22 |
Runtime error |
13 ms |
5332 KB |
Execution killed because of forbidden syscall gettid (186) |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
4668 KB |
Output is correct |
2 |
Correct |
0 ms |
4668 KB |
Output is correct |
3 |
Correct |
0 ms |
4668 KB |
Output is correct |
4 |
Correct |
0 ms |
4668 KB |
Output is correct |
5 |
Correct |
0 ms |
4668 KB |
Output is correct |
6 |
Correct |
0 ms |
4668 KB |
Output is correct |
7 |
Correct |
0 ms |
4668 KB |
Output is correct |
8 |
Correct |
0 ms |
4668 KB |
Output is correct |
9 |
Correct |
0 ms |
4668 KB |
Output is correct |
10 |
Correct |
0 ms |
4668 KB |
Output is correct |
11 |
Correct |
0 ms |
4668 KB |
Output is correct |
12 |
Correct |
0 ms |
4668 KB |
Output is correct |
13 |
Correct |
0 ms |
4668 KB |
Output is correct |
14 |
Correct |
0 ms |
4668 KB |
Output is correct |
15 |
Correct |
0 ms |
4668 KB |
Output is correct |
16 |
Correct |
0 ms |
4668 KB |
Output is correct |
17 |
Correct |
0 ms |
4668 KB |
Output is correct |
18 |
Correct |
0 ms |
4668 KB |
Output is correct |
19 |
Correct |
0 ms |
4668 KB |
Output is correct |
20 |
Correct |
0 ms |
4668 KB |
Output is correct |
21 |
Correct |
0 ms |
4668 KB |
Output is correct |
22 |
Runtime error |
0 ms |
4672 KB |
Execution killed because of forbidden syscall gettid (186) |
23 |
Halted |
0 ms |
0 KB |
- |