#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define sync ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define pb push_back
#define pii pair<int, int>
#define mp make_pair
#define fi first
#define se second
const int maxn = 3e4 + 10;
int n, k, lst;
vector<int> adj[maxn * 2], tmp[maxn * 2];
vector<int> cycle[maxn];
int s[maxn * 2], l[maxn * 2], r[maxn * 2], vis[maxn * 2], comp[maxn * 2], ans, N, E;
bool mark[maxn * 2];
vector<int> res, path;
void Dfs(int v, int p)
{
vis[v] = 1;
comp[v] = lst;
int tmp_res = 0;
for(int id : adj[v])
{
if(id == p)
continue;
int u = l[id] + r[id] - v;
if(!vis[u])
{
path.pb(id);
Dfs(u, id);
path.pop_back();
}
else if(vis[u] == 1)
{
//cout << v << " - " << u << endl;
path.pb(id);
int pnt = path.size() - 1;
while(pnt >= 0)
{
mark[l[path[pnt]]] = mark[r[path[pnt]]] = 1;
if(pnt % 2)
tmp_res += s[path[pnt]];
else
tmp_res -= s[path[pnt]];
// cout << l[path[pnt]] << " - " << r[path[pnt]] << " : " << s[path[pnt]] << endl;
cycle[lst].pb(path[pnt]);
if((l[path[pnt]] == u || r[path[pnt]] == u) && path[pnt] != id)
break;
pnt--;
}
/*mark[l[path[pnt]]] = mark[r[path[pnt]]] = 1;
cycle[lst].pb(path[pnt]);*/
/*if(pnt % 2)
tmp_res += s[path[pnt]];
else
tmp_res -= s[path[pnt]];*/
}
//cout << endl;
}
if(tmp_res)
{
//cout << lst << " : " << tmp_res << endl;
res.pb(tmp_res);
}
vis[v] = 2;
}
void Dfs2(int v, int p)
{
for(int id : adj[v])
{
int u = l[id] + r[id] - v;
if(mark[u] || u == p)
continue;
Dfs2(u, v);
if(u > n)
ans -= s[id];
else
ans += s[id];
}
return;
}
int main()
{
sync;
cin >> n >> k;
for(int i = 1; i <= 2 * n; i++)
{
cin >> l[i] >> r[i] >> s[i];
r[i] += n;
adj[l[i]].pb(i);
adj[r[i]].pb(i);
}
for(int i = 1; i <= 2 * n; i++)
{
if(!vis[i])
{
lst++;
N = 0;
E = 0;
Dfs(i, 0);
E /= 2;
if(N != E)
{
cout << "NO" << '\n';
return 0;
}
}
}
// cout << lst << endl;
for(int i = 1; i <= 2 * n; i++)
{
if(mark[i])
{
Dfs2(i, 0);
}
}
sort(res.begin(), res.end());
// reverse(res.begin(), res.end());
// cout << ans << endl;
for(int x : res)
{
if(ans < 0)
ans += abs(x);
else
ans += 0 - abs(x);
// cout << x << " : " << ans << endl;
}
if(abs(ans) > k)
cout << "NO" << '\n';
else
cout << "YES" << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3924 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
3796 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3924 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
3796 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
5388 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
5076 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3924 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
3796 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
