#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
bitset<2*20*30000+1> mile;
signed main()
{
int n, k;
cin >> n >> k;
vector<multiset<pii>> graph(2*n);
for (int i = 0; i < 2 * n; i++)
{
int a, b, c;
cin >> a >> b >> c;
graph[--a].insert({--b + n, c});
graph[b + n].insert({a, c});
}
set<pii> degs;
int sum = 0;
for (int i = 0; i < 2*n; i++)
degs.insert({graph[i].size(), i});
vector<int> vis(2*n,0);
auto brisi = [&](int i)
{
vis[i] = 1;
auto x = *graph[i].begin();
sum += x.ss * (i >= n ? -1 : 1);
degs.erase(degs.find({graph[x.ff].size(), x.ff}));
graph[x.ff].erase({i, x.ss});
degs.erase(degs.find({1, i}));
degs.insert({graph[x.ff].size(), x.ff});
};
while ((*degs.begin()).ff < 2)
{
auto x = *degs.begin();
if (x.ff == 0)
{
cout << "NO\n";
return 0;
}
brisi(x.ss);
}
if ((*degs.rbegin()).ff > 2)
{
cout << "NO\n";
return 0;
}
int ini = 0;
vector<int> cyc;
for (int i = 0; i < 2*n; i++)
{
if (!vis[i])
{
int idx = cyc.size();
cyc.push_back(0);
int cur = i;
int prev = i;
while(!vis[cur])
{
vis[cur] = 1;
auto x = *graph[cur].begin();
if (x.ff == prev)
x = *++graph[cur].begin();
prev = cur;
cyc[idx]+=(x.ff>=n?-1:1)*x.ss;
cur = x.ff;
}
//ini+=-abs(cyc[idx]);
}
}
const int hf = 20*30000;
mile[sum+hf] = 1;
for (auto x : cyc)
{
auto prev = mile;
mile=prev<<abs(x);
mile|=prev>>abs(x);
}
bool ther = 0;
for (int i = hf-k; i <= hf+k; i++)
ther|=mile[i];
cout << (ther?"YES\n":"NO\n");
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |