#include <fstream>
#include <cmath>
#include <vector>
#include <bitset>
#include <queue>
#include <cstring>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <cassert>
using namespace std;
#define pii pair<int, int>
#define f first
#define s second
#define ll long long
#define rint int32_t
const int siz = 6000000/100;
bitset<siz> bit;
ifstream cin("tug.in");
ofstream cout("tug.out");
struct Edge {
Edge(int lNA, int lNB, int lStrength) {
nA = lNA;
nB = lNB;
strength = lStrength;
}
int nA, nB, strength;
};
rint main() {
int n, tolerance;
cin >> n >> tolerance;
set<Edge*> graph [2*n];
for (int i = 0; i < 2*n; i++) {
int l, r, ls;
cin >> l >> r >> ls;
l--;
r--;
r += n;
Edge* e = new Edge(l, r, ls);
graph[l].insert(e);
graph[r].insert(e);
}
int desequilibrium = 0;
bool proc [2*n];
for (int i = 0; i < 2*n; i++) proc[i] = false;
queue<int> q;
for (int i = 0; i < 2*n; i++) {
if (graph[i].size() == 1) {
q.push(i);
}
}
while (!q.empty()) {
int curNode = q.front();
q.pop();
if (proc[curNode] or graph[curNode].empty()) continue;
proc[curNode] = true;
if (curNode < n) {
desequilibrium += (*(graph[curNode].begin()))->strength;
}
else {
desequilibrium -= (*(graph[curNode].begin()))->strength;
}
int newNode = (*(graph[curNode].begin()))->nA;
if (newNode == curNode) newNode = (*(graph[curNode].begin()))->nB;
graph[newNode].erase(graph[newNode].find(*(graph[curNode].begin())));
graph[curNode].clear();
if (graph[newNode].size() == 1) {
q.push(newNode);
}
}
desequilibrium = max(desequilibrium, -desequilibrium);
for (int i = 0; i < 2*n; i++) {
if (!proc[i] and graph[i].size() == 0) {
cout << "NO";
return 0;
}
}
vector<int> desequilibriums;
desequilibriums.push_back(desequilibrium);
int desequilibriumsSum = desequilibrium;
for (int i = 0; i < n; i++) {
if (proc[i]) continue;
int locDesiquilibrium = 0;
int curNode = i;
int parentNode = -1;
int step = 1;
while (!proc[curNode]) {
proc[curNode] = true;
int newNode = (*(graph[curNode].begin()))->nA;
if (newNode == curNode) newNode = (*(graph[curNode].begin()))->nB;
if (newNode == parentNode) {
newNode = (*(next(graph[curNode].begin())))->nA;
if (newNode == curNode) newNode = (*(next(graph[curNode].begin())))->nB;
locDesiquilibrium += step*(*(next(graph[curNode].begin())))->strength;
}
else {
locDesiquilibrium += step*(*(graph[curNode].begin()))->strength;
}
if (step == 1) step = -1;
else step = 1;
parentNode = curNode;
curNode = newNode;
}
locDesiquilibrium = max(locDesiquilibrium, -locDesiquilibrium);
desequilibriums.push_back(locDesiquilibrium);
desequilibriumsSum += locDesiquilibrium;
}
bit = bitset<siz>(0);
bit[0] = 1;
for (int i : desequilibriums) {
bit |= bit<<i;
}
for (int i = 0; i < siz; i++) if (bit[i] and abs(i-(desequilibriumsSum-i)) <= tolerance) {
cout << "YES";
return 0;
}
cout << "NO";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
