| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1000822 |
2024-06-18T09:41:31 Z |
LOLOLO |
Tug of War (BOI15_tug) |
C++17 |
|
6 ms |
3164 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f first
#define s second
#define pb push_back
#define ep emplace
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define mem(f,x) memset(f , x , sizeof(f))
#define sz(x) (ll)(x).size()
#define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b))
#define mxx *max_element
#define mnn *min_element
#define cntbit(x) __builtin_popcountll(x)
#define len(x) (int)(x.length())
const int N = 3e4 + 100;
set <pair <int, int>> ed[N];
bool used[N];
int st = 0;
pair <int, int> dfs(int u, int v) {
used[u] = 1;
if (u == st && v)
return {0, 0};
pair <int, int> A = {0, 0};
for (auto x : ed[u]) {
if (x.f == v)
continue;
A = dfs(x.f, u);
A.f += x.s;
swap(A.f, A.s);
}
return A;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, k;
cin >> n >> k;
int S = 0;
for (int i = 1; i <= n * 2; i++) {
int l, r, s;
cin >> l >> r >> s;
ed[l].insert({r + n, s});
ed[r + n].insert({l, s});
S += s;
}
queue <int> pq;
int sz = n * 2;
for (int i = 1; i <= sz; i++) {
if (sz(ed[i]) == 0) {
cout << "NO\n";
return 0;
}
if (sz(ed[i]) == 1)
pq.push(i);
}
int L = 0;
while (sz(pq)) {
int t = pq.front();
pq.pop();
if (sz(ed[t]) == 0) {
cout << "NO\n";
return 0;
}
auto it = *ed[t].begin();
int s = it.f, cost = it.s;
pair <int, int> pat = {t, cost};
ed[s].erase(pat);
ed[t].clear();
if (t <= n)
L += cost;
if (sz(ed[s]) == 1) {
pq.push(s);
}
}
for (int i = 1; i <= sz; i++) {
if (sz(ed[i]) > 2) {
cout << "NO\n";
return 0;
}
}
bitset <600001> dp;
dp[0] = 1;
for (int i = 1; i <= sz; i++) {
if (sz(ed[i]) == 2 && used[i] == 0) {
st = i;
pair <int, int> A = dfs(i, 0);
dp = (dp << A.f) | (dp << A.s);
}
}
for (int i = 0; i <= 600000; i++) {
if (dp[i]) {
if (abs((S - (L + i)) - (L+ i)) <= k) {
cout << "YES\n";
return 0;
}
}
}
cout << "NO\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2140 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2140 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2140 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2140 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2140 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2140 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2140 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
2140 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2140 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2140 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2140 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2140 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2140 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2140 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2140 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
2140 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
3164 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2140 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2140 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2140 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2140 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2140 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2140 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2140 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
2140 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
