This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 30005;
int n, k;
int l[2 * MAXN], r[2 * MAXN], s[2 * MAXN];
int pa, sum;
set <int> Adj[2 * MAXN];
set <int> D[2 * MAXN];
bool Used[2 * MAXN];
bitset <20 * MAXN> dp;
int c[2];
vector <int> N[2 * MAXN];
bool filled[2 * MAXN];
void DFS(int node, int color, int p = -1)
{
c[color] += s[node];
Used[node] = true;
for(auto x : N[node])
{
if(!Used[x])
{
DFS(x, 1 - color, node);
}
}
}
int main()
{
// freopen("Input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
priority_queue <pair <int, int> > pq;
cin >> n >> k;
for(int i = 1; i <= 2 * n; i++)
{
cin >> l[i] >> r[i] >> s[i];
sum += s[i];
Adj[l[i]].emplace(i);
Adj[r[i] + n].emplace(i);
D[l[i]].insert(i);
D[r[i] + n].insert(i);
}
for(int i = 1; i <= 2 * n; i++)
{
pq.emplace(-(int)D[i].size(), i);
}
while(pq.empty() == false)
{
int node = pq.top().second;
if(pq.top().first < -1)
{
break;
}
// cout << node << endl;
pq.pop();
if(D[node].empty())
{
cout << "NO\n";
return 0;
}
int tt = *D[node].begin();
if(node <= n)
{
pa += s[tt];
}
Used[tt] = true;
D[l[tt]].erase(tt);
D[r[tt] + n].erase(tt);
Adj[l[tt]].erase(tt);
Adj[r[tt] + n].erase(tt);
filled[node] = true;
if(!filled[l[tt]])
{
pq.emplace(-(int)D[l[tt]].size(), l[tt]);
}
if(!filled[r[tt] + n])
{
pq.emplace(-(int)D[r[tt] + n].size(), r[tt] + n);
}
}
for(int i = 1; i <= 2 * n; i++)
{
if(Adj[i].size() == 2)
{
int t1 = *Adj[i].begin();
Adj[i].erase(Adj[i].begin());
int t2 = *Adj[i].begin();
Adj[i].erase(t2);
N[t1].emplace_back(t2);
N[t2].emplace_back(t1);
}
}
dp[0] = 1;
for(int i = 1; i <= 2 * n; i++)
{
if(!Used[i])
{
c[0] = 0;
c[1] = 0;
DFS(i, 0);
int tmp = min(c[0], c[1]);
// cout << c[0] << ' ' << c[1] << endl;
pa += tmp;
dp = dp | (dp << (max(c[0], c[1]) - min(c[0], c[1])));
}
}
for(int i = 0; i <= sum; i++)
{
if(dp[i])
{
int t1 = i + pa;
int t2 = sum - t1;
if(abs(t1 - t2) <= k)
{
cout << "YES\n";
return 0;
}
}
}
cout << "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... |