#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44
using namespace std;
const int MAXVAL = 300000;
const int MAXN = 30000;
vector < pair <int, int> > g[4 * MAXN + 1];
bool vis[4 * MAXN + 1];
queue <int> Q;
int n;
void dfs(int nod, int &cur) {
vis[nod] = 1;
for(auto it : g[nod]) {
if(vis[it.first] == 0) {
if(it.first > 2 * n) {
if(it.first <= 3 * n) {
cur += it.second;
}
else {
cur -= it.second;
}
}
//cerr << nod << " " << it.first << " " << cur << "\n";
dfs(it.first, cur);
}
}
}
int deg[4 * MAXN + 1];
int main() {
//ifstream cin("A.in");
//ofstream cout("A.out");
int i, k;
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> k;
for(i = 1; i <= 2 * n; i++) {
int l, r, s;
cin >> l >> r >> s;
l += 2 * n;
r += 3 * n;
g[i].push_back({l, s});
g[l].push_back({i, s});
g[i].push_back({r, s});
g[r].push_back({i, s});
}
for(i = 2 * n + 1; i <= 4 * n; i++) {
if(g[i].size() == 1) {
Q.push(i);
vis[i] = 1;
}
}
int sl = 0, sr = 0;
while(Q.size()) {
int nod = Q.front();
Q.pop();
//cerr << nod << "\n";
for(auto it : g[nod]) {
if(vis[it.first] == 0) {
if(it.first <= 2 * n) {
vis[it.first] = 1;
Q.push(it.first);
if(nod <= 3 * n) {
sl += it.second;
}
else {
sr += it.second;
}
for(auto itr : g[it.first]) {
deg[itr.first]++;
}
}
else if(deg[it.first] + 1 == g[it.first].size()) {
vis[it.first] = 1;
Q.push(it.first);
}
}
}
}
//cerr << sl << " " << sr << "\n";
bitset < MAXVAL + 1 > bs;
bs[0] = 1;
int tot = 0;
for(i = 1; i <= 2 * n; i++) {
if(vis[i] == 0) {
int cur = 0;
dfs(i, cur);
cur = abs(cur);
tot += cur;
bs |= (bs << cur);
}
}
for(i = 0; i <= MAXVAL; i++) {
if(abs(sl - sr + tot - 2 * i) <= k && bs[i]) {
cout << "YES";
return 0;
}
}
cout << "NO";
//cin.close();
//cout.close();
return 0;
}
Compilation message
tug.cpp: In function 'int main()':
tug.cpp:83:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
else if(deg[it.first] + 1 == g[it.first].size()) {
~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
3220 KB |
Output is correct |
| 2 |
Correct |
4 ms |
3320 KB |
Output is correct |
| 3 |
Correct |
4 ms |
3192 KB |
Output is correct |
| 4 |
Correct |
4 ms |
3320 KB |
Output is correct |
| 5 |
Correct |
4 ms |
3320 KB |
Output is correct |
| 6 |
Correct |
5 ms |
3192 KB |
Output is correct |
| 7 |
Correct |
4 ms |
3320 KB |
Output is correct |
| 8 |
Correct |
5 ms |
3192 KB |
Output is correct |
| 9 |
Correct |
4 ms |
3320 KB |
Output is correct |
| 10 |
Correct |
4 ms |
3192 KB |
Output is correct |
| 11 |
Correct |
5 ms |
3192 KB |
Output is correct |
| 12 |
Correct |
4 ms |
3192 KB |
Output is correct |
| 13 |
Correct |
4 ms |
3320 KB |
Output is correct |
| 14 |
Correct |
4 ms |
3320 KB |
Output is correct |
| 15 |
Correct |
4 ms |
3320 KB |
Output is correct |
| 16 |
Correct |
4 ms |
3192 KB |
Output is correct |
| 17 |
Correct |
4 ms |
3192 KB |
Output is correct |
| 18 |
Correct |
4 ms |
3192 KB |
Output is correct |
| 19 |
Correct |
4 ms |
3324 KB |
Output is correct |
| 20 |
Correct |
4 ms |
3320 KB |
Output is correct |
| 21 |
Incorrect |
3 ms |
3320 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
3220 KB |
Output is correct |
| 2 |
Correct |
4 ms |
3320 KB |
Output is correct |
| 3 |
Correct |
4 ms |
3192 KB |
Output is correct |
| 4 |
Correct |
4 ms |
3320 KB |
Output is correct |
| 5 |
Correct |
4 ms |
3320 KB |
Output is correct |
| 6 |
Correct |
5 ms |
3192 KB |
Output is correct |
| 7 |
Correct |
4 ms |
3320 KB |
Output is correct |
| 8 |
Correct |
5 ms |
3192 KB |
Output is correct |
| 9 |
Correct |
4 ms |
3320 KB |
Output is correct |
| 10 |
Correct |
4 ms |
3192 KB |
Output is correct |
| 11 |
Correct |
5 ms |
3192 KB |
Output is correct |
| 12 |
Correct |
4 ms |
3192 KB |
Output is correct |
| 13 |
Correct |
4 ms |
3320 KB |
Output is correct |
| 14 |
Correct |
4 ms |
3320 KB |
Output is correct |
| 15 |
Correct |
4 ms |
3320 KB |
Output is correct |
| 16 |
Correct |
4 ms |
3192 KB |
Output is correct |
| 17 |
Correct |
4 ms |
3192 KB |
Output is correct |
| 18 |
Correct |
4 ms |
3192 KB |
Output is correct |
| 19 |
Correct |
4 ms |
3324 KB |
Output is correct |
| 20 |
Correct |
4 ms |
3320 KB |
Output is correct |
| 21 |
Incorrect |
3 ms |
3320 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
92 ms |
4728 KB |
Output is correct |
| 2 |
Correct |
27 ms |
4916 KB |
Output is correct |
| 3 |
Correct |
102 ms |
4728 KB |
Output is correct |
| 4 |
Incorrect |
25 ms |
4924 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
3220 KB |
Output is correct |
| 2 |
Correct |
4 ms |
3320 KB |
Output is correct |
| 3 |
Correct |
4 ms |
3192 KB |
Output is correct |
| 4 |
Correct |
4 ms |
3320 KB |
Output is correct |
| 5 |
Correct |
4 ms |
3320 KB |
Output is correct |
| 6 |
Correct |
5 ms |
3192 KB |
Output is correct |
| 7 |
Correct |
4 ms |
3320 KB |
Output is correct |
| 8 |
Correct |
5 ms |
3192 KB |
Output is correct |
| 9 |
Correct |
4 ms |
3320 KB |
Output is correct |
| 10 |
Correct |
4 ms |
3192 KB |
Output is correct |
| 11 |
Correct |
5 ms |
3192 KB |
Output is correct |
| 12 |
Correct |
4 ms |
3192 KB |
Output is correct |
| 13 |
Correct |
4 ms |
3320 KB |
Output is correct |
| 14 |
Correct |
4 ms |
3320 KB |
Output is correct |
| 15 |
Correct |
4 ms |
3320 KB |
Output is correct |
| 16 |
Correct |
4 ms |
3192 KB |
Output is correct |
| 17 |
Correct |
4 ms |
3192 KB |
Output is correct |
| 18 |
Correct |
4 ms |
3192 KB |
Output is correct |
| 19 |
Correct |
4 ms |
3324 KB |
Output is correct |
| 20 |
Correct |
4 ms |
3320 KB |
Output is correct |
| 21 |
Incorrect |
3 ms |
3320 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
