| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 337719 |
2020-12-21T12:40:43 Z |
HynDuf |
Tug of War (BOI15_tug) |
C++11 |
|
4 ms |
4588 KB |
#include <bits/stdc++.h>
#define F first
#define S second
#define eb emplace_back
#define pb push_back
#define pf push_front
#define all(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define Rep(i, r, l) for (int i = (r); i >= (l); i--)
#define DB(X) {cerr << #X << " = " << X << '\n';}
#define DB1(A, _) {cerr << #A << "[" << _ << "] = " << A[_] << '\n';}
#define DB2(A, _, __) {cerr << #A << "[" << _ << "][" << __ << "] = " << A[_][__] << '\n';}
#define DB3(A, _, __, ____) {cerr << #A << "[" << _ << "][" << __ << "][" << ___ << "] = " << A[_][__][___] << '\n';}
#define PR(A, l, r) {cerr << '\n'; rep(_, l, r) DB1(A, _); cerr << '\n';}
#define left ___left
#define right ___right
#define next ___next
#define prev ___prev
#define y1 ___y1
#define y0 ___y0
#define j0 ___j0
#define SZ(x) ((int)(x).size())
using ll = long long;
using ld = long double;
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef vector<ii> vii;
typedef vector<ll> vl;
const int N = 6e4 + 2, NN = 600002;
int n, cnt[N], K;
struct Tug
{
int l, r, s;
} tug[N];
set<int> tu[N];
vii g[N];
vi obj;
bool vis[N];
int cur;
void dfs(int u, int r)
{
for (const ii &v : g[u]) if (!vis[v.S])
{
vis[v.S] = 1;
if (u > n) cur -= tug[v.S].s;
else cur += tug[v.S].s;
if (v.F != r) dfs(v.F, r);
}
}
bitset<NN> dp;
int main()
{
freopen("T.in", "r", stdin);
// ios_base::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> K;
rep(i, 1, n << 1)
{
int l, r, s;
cin >> l >> r >> s;
r += n;
tug[i] = {l, r, s};
cnt[l]++, cnt[r]++;
tu[l].insert(i);
tu[r].insert(i);
}
queue<int> q;
rep(i, 1, (n << 1)) if (cnt[i] == 0)
{
cout << "NO";
return 0;
} else if (cnt[i] == 1) q.push(i);
int ans = 0;
while (!q.empty())
{
int u = q.front();
q.pop();
if (cnt[u] == 0)
{
cout << "NO";
return 0;
}
assert(cnt[u] == 1);
assert(SZ(tu[u]) == 1);
cnt[u] = 0;
int id = *tu[u].begin();
int ano = (tug[id].l == u ? tug[id].r : tug[id].l);
if (--cnt[ano] == 1) q.push(ano);
if (u > n) ans -= tug[id].s;
else ans += tug[id].s;
tu[ano].erase(id);
}
rep(u, 1, (n << 1)) if (cnt[u])
{
assert(cnt[u] == 2);
assert(SZ(tu[u]) == 2);
auto it = tu[u].begin();
int ano = (tug[*it].l == u ? tug[*it].r : tug[*it].l);
g[u].eb(ano, *it);
it++;
ano = (tug[*it].l == u ? tug[*it].r : tug[*it].l);
g[u].eb(ano, *it);
}
rep(i, 1, (n << 1)) if (cnt[i] == 2 && !vis[i])
{
cur = 0;
dfs(i, i);
obj.eb(abs(cur));
//DB(cur);
}
dp[0] = 1;
for (int v : obj) dp = (dp << v) | (dp >> v);
rep(i, 0, K) if (dp[i])
{
cout << "YES";
return 0;
}
cout << "NO";
return 0;
}
Compilation message
tug.cpp: In function 'int main()':
tug.cpp:55:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
55 | freopen("T.in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4588 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
4588 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
