这场本来能AK的,做的时候不知道为什么脑子抽了B题一直调不过去,F题像天梯赛原题,出边写错了一直没调出来。。。
A - Food for Animals
/***
* author: wrz
* created: 05.05.2022 21:56:58
*/
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "../template/debug.hpp"
#else
#define debug(...) 42
#endif
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int tt;
cin >> tt;
while (tt--) {
int a, b, c, x, y;
cin >> a >> b >> c >> x >> y;
if (a >= x && b >= y) {
cout << "YES\n";
} else {
if (a + c < x || b + c < y) {
cout << "NO\n";
} else {
if (a + b + c >= x + y) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
}
}
return 0;
}
B - Make It Increasing
/***
* author: wrz
* created: 05.05.2022 22:43:12
*/
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "../template/debug.hpp"
#else
#define debug(...) 42
#endif
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int ans = 0;
bool bad = false;
for (int i = n - 2; i >= 0; i--) {
if (a[i + 1] == 0) {
bad = true;
break;
}
while (a[i] >= a[i + 1]) {
a[i] >>= 1;
ans++;
}
}
if (!bad && is_sorted(a.begin(), a.end())) {
cout << ans << '\n';
} else {
cout << "-1\n";
}
}
return 0;
}
C - Detective Task
/***
* author: wrz
* created: 05.05.2022 23:39:38
*/
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "../template/debug.hpp"
#else
#define debug(...) 42
#endif
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int tt;
cin >> tt;
while (tt--) {
string s;
cin >> s;
if (s.size() == 1) {
cout << "1\n";
continue;
}
int p0 = -1, p1 = -1;
for (int i = 0; i < (int) s.size(); i++) {
if (p0 == -1 && s[i] == '0') {
p0 = i;
}
if (s[i] == '1') {
p1 = max(p1, i);
}
}
debug(p0, p1);
if (p0 == -1 && p1 == -1) {
cout << s.size() << '\n';
} else if (p0 == -1) {
cout << s.size() - p1 << '\n';
} else if (p1 == -1) {
cout << p0 + 1 << '\n';
} else {
cout << p0 - p1 + 1 << '\n';
}
}
return 0;
}
D - Vertical Paths
/***
* author: wrz
* created: 05.05.2022 22:53:20
*/
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "../template/debug.hpp"
#else
#define debug(...) 42
#endif
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
int root = 0;
vector<int> nxt(n + 1, 0);
vector<int> head(n + 1, 0);
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (a[i] == i) {
root = i;
continue;
}
nxt[i] = head[a[i]];
head[a[i]] = i;
}
int k = 0;
vector<int> dfn(n + 1);
vector<int> hs(n + 1);
function<void(int, int)> dfs = [&](int u, int pr) {
if (pr) {
dfn[++k] = u;
}
hs[u] = head[u];
if (hs[u]) {
dfs(hs[u], 0);
}
for (int i = nxt[head[u]]; i != 0; i = nxt[i]) {
dfs(i, 1);
}
};
dfs(root, 1);
cout << k << '\n';
for (int i = 1; i <= k; i++) {
int x = dfn[i];
int s = 0;
while (x) {
x = hs[x];
++s;
}
cout << s << '\n';
x = dfn[i];
while (s--) {
cout << x << " \n"[s == 0];
x = hs[x];
}
}
cout << '\n';
}
return 0;
}
E - Replace With the Previous, Minimize
/***
* author: wrz
* created: 05.05.2022 23:04:15
*/
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "../template/debug.hpp"
#else
#define debug(...) 42
#endif
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int tt;
cin >> tt;
while (tt--) {
int n, k;
cin >> n >> k;
string s;
cin >> s;
if (k == 0) {
cout << s << '\n';
continue;
}
char mx = 'a';
for (int i = 0; i < n; i++) {
int x = s[i] - mx;
if (x <= 0) continue;
x = min(x, k);
char r;
if (s[i] - x <= mx) {
r = 'a';
} else {
r = s[i] - x;
}
char t = s[i];
for (auto &j : s) {
if (j <= t && j > mx) {
j = min(j, r);
}
}
k -= x;
mx = t;
}
cout << s << '\n';
}
return 0;
}
F - Vlad and Unfinished Business
/***
* author: wrz
* created: 05.05.2022 23:17:23
*/
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "../template/debug.hpp"
#else
#define debug(...) 42
#endif
template <typename T>
class graph {
public:
struct edge {
int from;
int to;
T cost;
};
vector<edge> edges;
vector<vector<int> > g;
int n;
function<bool(int)> ignore;
graph(int _n) : n(_n) {
g.resize(n);
ignore = nullptr;
}
virtual int add(int from, int to, T cost) = 0;
virtual void set_ignore_edge_rule(const function<bool(int)> &f) {
ignore = f;
}
virtual void reset_ignore_edge_rule() { ignore = nullptr; }
};
template <typename T>
class forest : public graph<T> {
public:
using graph<T>::edges;
using graph<T>::g;
using graph<T>::n;
forest(int _n) : graph<T>(_n) {}
int add(int from, int to, T cost = 1) {
assert(0 <= from && from < n && 0 <= to && to < n);
int id = (int)edges.size();
assert(id < n - 1);
g[from].push_back(id);
g[to].push_back(id);
edges.push_back({from, to, cost});
return id;
}
};
template <typename T>
class dfs_forest : public forest<T> {
public:
using forest<T>::edges;
using forest<T>::g;
using forest<T>::n;
using forest<T>::ignore;
vector<int> pv;
vector<int> pe;
vector<int> order;
vector<int> pos;
vector<int> end;
vector<int> sz;
vector<int> root;
vector<int> depth;
vector<T> dist;
dfs_forest(int _n) : forest<T>(_n) {
}
void init() {
pv = vector<int>(n, -1);
pe = vector<int>(n, -1);
order.clear();
pos = vector<int>(n, -1);
end = vector<int>(n, -1);
sz = vector<int>(n, 0);
root = vector<int>(n, -1);
depth = vector<int>(n, -1);
dist = vector<T>(n);
}
void clear() {
pv.clear();
pe.clear();
order.clear();
pos.clear();
end.clear();
sz.clear();
root.clear();
depth.clear();
dist.clear();
}
private:
void do_dfs(int v) {
pos[v] = (int) order.size();
order.push_back(v);
sz[v] = 1;
for (int id : g[v]) {
if (id == pe[v] || (ignore != nullptr && ignore(id))) {
continue;
}
auto &e = edges[id];
int to = e.from ^ e.to ^ v;
depth[to] = depth[v] + 1;
dist[to] = dist[v] + e.cost;
pv[to] = v;
pe[to] = id;
root[to] = (root[v] != -1 ? root[v] : to);
do_dfs(to);
sz[v] += sz[to];
}
end[v] = (int) order.size() - 1;
}
void do_dfs_from(int v) {
depth[v] = 0;
dist[v] = T{};
root[v] = v;
pv[v] = pe[v] = -1;
do_dfs(v);
}
public:
void dfs(int v, bool clear_order = true) {
if (pv.empty()) {
init();
} else {
if (clear_order) {
order.clear();
}
}
do_dfs_from(v);
}
void dfs_all() {
init();
for (int v = 0; v < n; v++) {
if (depth[v] == -1) {
do_dfs_from(v);
}
}
assert((int) order.size() == n);
}
};
template <typename T>
class lca_forest : public dfs_forest<T> {
public:
using dfs_forest<T>::edges;
using dfs_forest<T>::g;
using dfs_forest<T>::n;
using dfs_forest<T>::pv;
using dfs_forest<T>::pos;
using dfs_forest<T>::end;
using dfs_forest<T>::depth;
int h;
vector<vector<int> > pr;
lca_forest(int _n) : dfs_forest<T>(_n) {}
inline void build_lca() {
assert(!pv.empty());
int max_depth = 0;
for (int i = 0; i < n; i++) {
max_depth = max(max_depth, depth[i]);
}
h = 1;
while ((1 << h) <= max_depth) {
h++;
}
pr.resize(n);
for (int i = 0; i < n; i++) {
pr[i].resize(h);
pr[i][0] = pv[i];
}
for (int j = 1; j < h; j++) {
for (int i = 0; i < n; i++) {
pr[i][j] = (pr[i][j - 1] == -1 ? -1 : pr[pr[i][j - 1]][j - 1]);
}
}
}
inline bool anc(int x, int y) {
return (pos[x] <= pos[y] && end[y] <= end[x]);
}
inline int lca(int x, int y) {
// maybe
// if depth[x] > depth[y], swap
// then go from j = log(depth[x])?
assert(!pr.empty());
if (anc(x, y)) {
return x;
}
if (anc(y, x)) {
return y;
}
for (int j = h - 1; j >= 0; j--) {
if (pr[x][j] != -1 && !anc(pr[x][j], y)) {
x = pr[x][j];
}
}
return pr[x][0];
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int tt;
cin >> tt;
while (tt--) {
int n, k, x, y;
cin >> n >> k >> x >> y;
--x, --y;
vector<int> a(k);
for (int i = 0; i < k; i++) {
cin >> a[i];
a[i]--;
}
lca_forest<int> g(n);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
--u, --v;
g.add(u, v);
}
g.dfs(0);
g.build_lca();
vector<int> w(n, 0);
for (int i = 0; i < k; i++) {
int lax = g.lca(a[i], x);
w[a[i]]++;
w[x]++;
w[lax] -= 2;
}
int lxy = g.lca(x, y);
w[x]++;
w[y]++;
w[lxy] -= 2;
int ans = 0;
auto Ask = [&](auto self, int u, int pr) -> void {
for (auto id : g.g[u]) {
if (id == g.pe[u]) continue;
auto &e = g.edges[id];
int to = e.from ^ e.to ^ u;
if (to == pr) continue;
self(self, to, u);
w[u] += w[to]; // w[to] not w[e.to] wo shi sha BBBBBBBBBBBBBBBB
}
if (w[u]) {
ans += 2;
}
};
Ask(Ask, 0, 0);
cout << ans - (g.dist[x] + g.dist[y] - 2 * g.dist[lxy]) << '\n';
}
return 0;
}
G - Sorting Pancakes
/***
* author: wrz
* created: 05.05.2022 23:30:43
*/
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "../template/debug.hpp"
#else
#define debug(...) 42
#endif
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<int> pref(n + 1);
for (int i = 1; i <= n; i++) {
cin >> pref[i];
pref[i] += pref[i - 1];
}
vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(m + 1, vector<int>(m + 1, (int)1e9)));
dp[0][m][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
for (int k = 0; k + j <= m; k++) {
for (int s = k; s <= j; s++) {
// assert(n - i >= 1);
dp[i][j - s][s] = min(dp[i][j - s][s], dp[i - 1][j][k] + abs(j - s - pref[n - i]));
}
}
}
}
cout << *min_element(dp[n][0].begin(), dp[n][0].end()) << '\n';
return 0;
}