We hope you enjoyed the problems!↵
↵
<spoiler summary="Rate the contest!">↵
↵
<spoiler summary="Quality">↵
↵
- [likes:1,option1] Excellent contest↵
- [likes:1,option2] Good contest↵
- [likes:1,option3] Average contest↵
- [likes:1,option4] Bad contest↵
- [likes:1,option5] Horrible contest↵
↵
</spoiler>↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:2,option1] Trivial contest↵
- [likes:2,option2] Easy contest↵
- [likes:2,option3] Average contest↵
- [likes:2,option4] Hard contest↵
- [likes:2,option5] Impossible contest↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
[problem:2245A]↵
↵
<spoiler summary="Solution">↵
[tutorial:2245A] ↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
for _ in range(int(input())):↵
n, k = map(int, input().split())↵
s = input()↵
if k * 2 > n:↵
print(-1)↵
continue↵
ans = 0↵
for i in range(k):↵
ans += int(s[i] != 'R') + int(s[n - i - 1] != 'L')↵
print(ans)↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Quality">↵
↵
- [likes:3,option1] Excellent problem↵
- [likes:3,option2] Good problem↵
- [likes:3,option3] Average problem↵
- [likes:3,option4] Bad problem↵
- [likes:3,option5] Horrible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:4,option1] Trivial problem↵
- [likes:4,option2] Easy problem↵
- [likes:4,option3] Average problem↵
- [likes:4,option4] Hard problem↵
- [likes:4,option5] Impossible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
[problem:2245B]↵
↵
<spoiler summary="Solution">↵
[tutorial:2245B] ↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
for _ in range(int(input())):↵
n, c = map(int, input().split())↵
a = list(map(int, input().split()))↵
a.sort()↵
for i in range(n):↵
a[i] -= c↵
for i in range(n // 2):↵
a[i] = max(a[i], 0)↵
print(sum(a))↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Quality">↵
↵
- [likes:5,option1] Excellent problem↵
- [likes:5,option2] Good problem↵
- [likes:5,option3] Average problem↵
- [likes:5,option4] Bad problem↵
- [likes:5,option5] Horrible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:6,option1] Trivial problem↵
- [likes:6,option2] Easy problem↵
- [likes:6,option3] Average problem↵
- [likes:6,option4] Hard problem↵
- [likes:6,option5] Impossible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
[problem:2245C]↵
↵
<spoiler summary="Solution">↵
[tutorial:2245C] ↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
for _ in range(int(input())):↵
n, k = map(int, input().split())↵
if n == 1:↵
if k == 1:↵
print("YES")↵
print(0)↵
else:↵
print("NO")↵
continue↵
k ^= n↵
if k.bit_length() > (n - 1).bit_length():↵
print("NO")↵
continue↵
s = list()↵
if 0 < k <= n - 1:↵
s.append(k)↵
elif k:↵
s.append(n - 1)↵
s.append((n - 1) ^ k)↵
s.append(0)↵
a = s[:]↵
for i in range(n):↵
if i not in s:↵
a.append(i)↵
print("YES")↵
print(*reversed(a))↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Quality">↵
↵
- [likes:7,option1] Excellent problem↵
- [likes:7,option2] Good problem↵
- [likes:7,option3] Average problem↵
- [likes:7,option4] Bad problem↵
- [likes:7,option5] Horrible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:8,option1] Trivial problem↵
- [likes:8,option2] Easy problem↵
- [likes:8,option3] Average problem↵
- [likes:8,option4] Hard problem↵
- [likes:8,option5] Impossible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
[problem:2245D1]↵
↵
<spoiler summary="Solution">↵
[tutorial:2245D1] ↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
void solve() {↵
int n, m;↵
std::cin >> n >> m;↵
std::vector b(n, std::vector<int>(n));↵
while (m--) {↵
int o, i, j;↵
std::cin >> o >> i >> j;↵
i--;↵
j--;↵
b[i][j] = b[j][i] = o;↵
}↵
std::vector<std::vector<int>> g(n);↵
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {↵
if (b[i][i] == 1 && b[j][j] == 2) {↵
if (b[i][j] == 1) g[j].push_back(i);↵
else g[i].push_back(j);↵
}↵
}↵
std::vector<int> d(n), ans(n);↵
for (int u = 0; u < n; u++) for (auto v : g[u]) d[v]++;↵
int cnt = 0;↵
std::queue<int> q;↵
for (int u = 0; u < n; u++) if (!d[u]) q.push(u);↵
while (!q.empty()) {↵
int u = q.front();↵
q.pop();↵
if (b[u][u] == 1) ans[u] = ++cnt;↵
else ans[u] = -(++cnt);↵
for (auto v : g[u]) if (!--d[v]) q.push(v);↵
}↵
if (cnt == n) {↵
for (int i = 0; i < n; i++) for (int j = i; j < n; j++) {↵
if (b[i][j] == 1 && ans[i] + ans[j] < 0) return void(std::cout << "NO\n");↵
if (b[i][j] == 2 && ans[i] + ans[j] >= 0) return void(std::cout << "NO\n");↵
}↵
std::cout << "YES\n";↵
for (int i = 0; i < n; i++) std::cout << ans[i] << " \n"[i + 1 == n];↵
} else {↵
std::cout << "NO\n";↵
}↵
}↵
↵
int main() {↵
std::ios::sync_with_stdio(0);↵
std::cin.tie(0);↵
↵
int t;↵
std::cin >> t;↵
while (t--) solve();↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Quality">↵
↵
- [likes:9,option1] Excellent problem↵
- [likes:9,option2] Good problem↵
- [likes:9,option3] Average problem↵
- [likes:9,option4] Bad problem↵
- [likes:9,option5] Horrible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:10,option1] Trivial problem↵
- [likes:10,option2] Easy problem↵
- [likes:10,option3] Average problem↵
- [likes:10,option4] Hard problem↵
- [likes:10,option5] Impossible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
[problem:2245D2]↵
↵
<spoiler summary="Solution">↵
[tutorial:2245D2] ↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
void solve() {↵
int n, m;↵
std::cin >> n >> m;↵
std::vector d(2, std::vector<int>(n));↵
std::vector<std::vector<std::pair<int, int>>> g(n);↵
while (m--) {↵
int o, i, j;↵
std::cin >> o >> i >> j;↵
o--;↵
i--;↵
j--;↵
g[i].emplace_back(j, o);↵
g[j].emplace_back(i, o);↵
d[o][i]++;↵
d[o][j]++;↵
}↵
std::queue<int> q;↵
std::vector<bool> vis(n);↵
for (int i = 0; i < n; i++) if (d[0][i] == 0 || d[1][i] == 0) q.push(i), vis[i] = true;↵
std::vector<std::pair<int, int>> t;↵
while (!q.empty()) {↵
int u = q.front();↵
q.pop();↵
if (d[0][u] == 0) t.emplace_back(u, -1);↵
else t.emplace_back(u, 1);↵
for (auto [v, o] : g[u]) if (!--d[o][v] && !vis[v]) {↵
vis[v] = true;↵
q.push(v);↵
}↵
}↵
if (t.size() < n) return void(std::cout << "NO\n");↵
std::cout << "YES\n";↵
std::vector<int> ans(n);↵
std::reverse(t.begin(), t.end());↵
for (int i = 0; i < n; i++) ans[t[i].first] = (i + 1) * t[i].second;↵
for (int i = 0; i < n; i++) std::cout << ans[i] << " \n"[i + 1 == n];↵
}↵
↵
int main() {↵
std::ios::sync_with_stdio(0);↵
std::cin.tie(0);↵
↵
int t;↵
std::cin >> t;↵
while (t--) solve();↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Quality">↵
↵
- [likes:11,option1] Excellent problem↵
- [likes:11,option2] Good problem↵
- [likes:11,option3] Average problem↵
- [likes:11,option4] Bad problem↵
- [likes:11,option5] Horrible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:12,option1] Trivial problem↵
- [likes:12,option2] Easy problem↵
- [likes:12,option3] Average problem↵
- [likes:12,option4] Hard problem↵
- [likes:12,option5] Impossible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
[problem:2245E]↵
↵
<spoiler summary="Solution">↵
[tutorial:2245E] ↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
void solve() {↵
int n;↵
std::cin >> n;↵
std::vector<std::vector<int>> g(n);↵
for (int i = 0; i < n - 1; i++) {↵
int u, v;↵
std::cin >> u >> v;↵
u--;↵
v--;↵
g[u].push_back(v);↵
g[v].push_back(u);↵
}↵
std::vector<bool> vis(n);↵
long long ans = 0;↵
int c = 0;↵
auto dfs = [&](auto&& self, int u) -> void {↵
vis[u] = true;↵
for (auto v : g[u]) {↵
if (g[v].size() & 1) ans += c++;↵
else if (!vis[v]) self(self, v);↵
}↵
};↵
for (int u = 0; u < n; u++) if (~g[u].size() & 1 && !vis[u]) {↵
c = 0;↵
dfs(dfs, u);↵
}↵
for (int u = 0; u < n; u++) for (auto v : g[u]) if (v > u) ans += g[u].size() & g[v].size() & 1;↵
std::cout << ans << "\n";↵
}↵
↵
int main() {↵
std::ios::sync_with_stdio(0);↵
std::cin.tie(0);↵
↵
int t;↵
std::cin >> t;↵
while (t--) solve();↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Quality">↵
↵
- [likes:13,option1] Excellent problem↵
- [likes:13,option2] Good problem↵
- [likes:13,option3] Average problem↵
- [likes:13,option4] Bad problem↵
- [likes:13,option5] Horrible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:14,option1] Trivial problem↵
- [likes:14,option2] Easy problem↵
- [likes:14,option3] Average problem↵
- [likes:14,option4] Hard problem↵
- [likes:14,option5] Impossible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
[problem:2245F]↵
↵
<spoiler summary="Solution">↵
[tutorial:2245F] ↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
M = 998244353↵
N = 501↵
fac = [0] * N↵
fac[0] = 1↵
for i in range(1, N):↵
fac[i] = fac[i - 1] * i % M↵
inv = [0] * N↵
inv[-1] = pow(fac[-1], M - 2, M)↵
for i in range(N - 2, -1, -1):↵
inv[i] = inv[i + 1] * (i + 1) % M↵
def comb(n, k):↵
if k < 0 or k > n:↵
return 0↵
return fac[n] * inv[k] % M * inv[n - k] % M↵
↵
for _ in range(int(input())):↵
n = int(input())↵
a = list(map(int, input().split()))↵
if sum(max(0, v) for v in a) >= n:↵
print(0)↵
continue↵
a.append(-1)↵
f = [[[0] for _ in range(n)] for _ in range(n + 1)]↵
g = [[0] * n for _ in range(n + 1)]↵
for r in range(n):↵
if a[r + 1] != -1:↵
for l in range(n):↵
f[l][r] = [0] * (a[r + 1] + 1)↵
for i in range(1, n + 1):↵
f[i][i - 1][0] = 1↵
g[i][i - 1] = 1↵
def w(i, k):↵
if i == k:↵
return 1 if a[k] <= 0 else 0↵
else:↵
return f[i][k - 1][a[k]] if a[k] != -1 else g[i][k - 1]↵
for l in range(n - 1, -1, -1):↵
for r in range(l, n):↵
if a[r + 1] == -1:↵
for k in range(l, r + 1):↵
g[l][r] = (g[l][r] + comb(r - l, k - l) * w(l, k) % M * g[k + 1][r] % M) % M↵
else:↵
for c in range(1, a[r + 1] + 1):↵
for k in range(l, r + 1):↵
f[l][r][c] = (f[l][r][c] + comb(r - l, k - l) * w(l, k) % M * f[k + 1][r][c - 1] % M) % M↵
print(w(0, n))↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Quality">↵
↵
- [likes:15,option1] Excellent problem↵
- [likes:15,option2] Good problem↵
- [likes:15,option3] Average problem↵
- [likes:15,option4] Bad problem↵
- [likes:15,option5] Horrible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:16,option1] Trivial problem↵
- [likes:16,option2] Easy problem↵
- [likes:16,option3] Average problem↵
- [likes:16,option4] Hard problem↵
- [likes:16,option5] Impossible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
[problem:2245G]↵
↵
<spoiler summary="Solution">↵
[tutorial:2245G] ↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
std::string query(const std::vector<int>& a) {↵
std::cout << "? " << a.size();↵
for (auto v : a) std::cout << " " << v + 1;↵
std::cout << std::endl;↵
std::string s;↵
std::cin >> s;↵
return s;↵
}↵
↵
std::vector<int> work(const std::vector<int>& a, const std::vector<int>& b) {↵
if (a.empty() || b.empty()) return {};↵
std::vector<int> s;↵
for (auto v : a) s.push_back(v);↵
for (auto v : b) s.push_back(v);↵
std::string t = query(s);↵
std::vector<int> r;↵
for (int i = 0; i < b.size(); i++) if (t[i + a.size()] == '0') r.push_back(b[i]);↵
return r;↵
}↵
↵
void solve() {↵
int n;↵
std::cin >> n;↵
std::vector<std::vector<int>> g(n);↵
auto find = [&](auto&& self, std::vector<int> a, std::vector<int> b) -> void {↵
if (a.empty() || b.empty()) return;↵
if (a.size() == 1) {↵
for (auto v : b) g[v].push_back(a[0]), g[a[0]].push_back(v);↵
return;↵
}↵
int m = a.size() / 2;↵
std::vector a1(a.begin(), a.begin() + m), a2(a.begin() + m, a.end());↵
auto p1 = work(a1, b);↵
std::set<int> vis(p1.begin(), p1.end());↵
std::vector<int> nb, p2;↵
for (auto v : b) {↵
if (vis.count(v)) nb.push_back(v);↵
else p2.push_back(v);↵
}↵
self(self, a1, p1);↵
for (auto v : work(a2, nb)) p2.push_back(v);↵
self(self, a2, p2);↵
};↵
auto dfs = [&](auto&& self, std::vector<int> a) -> void {↵
if (a.size() <= 1) return;↵
std::string t = query(a);↵
std::vector<int> p1, p2;↵
for (int i = 0; i < a.size(); i++) {↵
if (t[i] == '0') p2.push_back(a[i]);↵
else p1.push_back(a[i]);↵
}↵
self(self, p2);↵
std::vector<int> col(n, -1);↵
std::vector<std::vector<int>> b(2);↵
for (auto w : p2) if (col[w] == -1) {↵
std::queue<int> q;↵
q.push(w);↵
col[w] = 0;↵
while (!q.empty()) {↵
int u = q.front();↵
q.pop();↵
b[col[u]].push_back(u);↵
for (auto v : g[u]) if (col[v] == -1) {↵
col[v] = col[u] ^ 1;↵
q.push(v);↵
}↵
}↵
}↵
for (int i = 0; i < 2; i++) {↵
find(find, b[i], work(b[i], p1));↵
}↵
};↵
std::vector<int> a(n);↵
std::iota(a.begin(), a.end(), 0);↵
dfs(dfs, a);↵
std::cout << "!" << std::endl;↵
for (int u = 0; u < n; u++) for (auto v : g[u]) if (v > u) std::cout << u + 1 << " " << v + 1 << std::endl;↵
}↵
↵
int main() {↵
std::ios::sync_with_stdio(0);↵
std::cin.tie(0);↵
↵
int t;↵
std::cin >> t;↵
while (t--) solve();↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Quality">↵
↵
- [likes:17,option1] Excellent problem↵
- [likes:17,option2] Good problem↵
- [likes:17,option3] Average problem↵
- [likes:17,option4] Bad problem↵
- [likes:17,option5] Horrible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:18,option1] Trivial problem↵
- [likes:18,option2] Easy problem↵
- [likes:18,option3] Average problem↵
- [likes:18,option4] Hard problem↵
- [likes:18,option5] Impossible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
[problem:2245H]↵
↵
<spoiler summary="Solution">↵
Tutorial will be added after the first official solve.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Quality">↵
↵
- [likes:19,option1] Excellent problem↵
- [likes:19,option2] Good problem↵
- [likes:19,option3] Average problem↵
- [likes:19,option4] Bad problem↵
- [likes:19,option5] Horrible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:20,option1] Trivial problem↵
- [likes:20,option2] Easy problem↵
- [likes:20,option3] Average problem↵
- [likes:20,option4] Hard problem↵
- [likes:20,option5] Impossible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Rate the contest!">↵
↵
<spoiler summary="Quality">↵
↵
- [likes:1,option1] Excellent contest↵
- [likes:1,option2] Good contest↵
- [likes:1,option3] Average contest↵
- [likes:1,option4] Bad contest↵
- [likes:1,option5] Horrible contest↵
↵
</spoiler>↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:2,option1] Trivial contest↵
- [likes:2,option2] Easy contest↵
- [likes:2,option3] Average contest↵
- [likes:2,option4] Hard contest↵
- [likes:2,option5] Impossible contest↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
[problem:2245A]↵
↵
<spoiler summary="Solution">↵
[tutorial:2245A] ↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
for _ in range(int(input())):↵
n, k = map(int, input().split())↵
s = input()↵
if k * 2 > n:↵
print(-1)↵
continue↵
ans = 0↵
for i in range(k):↵
ans += int(s[i] != 'R') + int(s[n - i - 1] != 'L')↵
print(ans)↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Quality">↵
↵
- [likes:3,option1] Excellent problem↵
- [likes:3,option2] Good problem↵
- [likes:3,option3] Average problem↵
- [likes:3,option4] Bad problem↵
- [likes:3,option5] Horrible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:4,option1] Trivial problem↵
- [likes:4,option2] Easy problem↵
- [likes:4,option3] Average problem↵
- [likes:4,option4] Hard problem↵
- [likes:4,option5] Impossible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
[problem:2245B]↵
↵
<spoiler summary="Solution">↵
[tutorial:2245B] ↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
for _ in range(int(input())):↵
n, c = map(int, input().split())↵
a = list(map(int, input().split()))↵
a.sort()↵
for i in range(n):↵
a[i] -= c↵
for i in range(n // 2):↵
a[i] = max(a[i], 0)↵
print(sum(a))↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Quality">↵
↵
- [likes:5,option1] Excellent problem↵
- [likes:5,option2] Good problem↵
- [likes:5,option3] Average problem↵
- [likes:5,option4] Bad problem↵
- [likes:5,option5] Horrible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:6,option1] Trivial problem↵
- [likes:6,option2] Easy problem↵
- [likes:6,option3] Average problem↵
- [likes:6,option4] Hard problem↵
- [likes:6,option5] Impossible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
[problem:2245C]↵
↵
<spoiler summary="Solution">↵
[tutorial:2245C] ↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
for _ in range(int(input())):↵
n, k = map(int, input().split())↵
if n == 1:↵
if k == 1:↵
print("YES")↵
print(0)↵
else:↵
print("NO")↵
continue↵
k ^= n↵
if k.bit_length() > (n - 1).bit_length():↵
print("NO")↵
continue↵
s = list()↵
if 0 < k <= n - 1:↵
s.append(k)↵
elif k:↵
s.append(n - 1)↵
s.append((n - 1) ^ k)↵
s.append(0)↵
a = s[:]↵
for i in range(n):↵
if i not in s:↵
a.append(i)↵
print("YES")↵
print(*reversed(a))↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Quality">↵
↵
- [likes:7,option1] Excellent problem↵
- [likes:7,option2] Good problem↵
- [likes:7,option3] Average problem↵
- [likes:7,option4] Bad problem↵
- [likes:7,option5] Horrible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:8,option1] Trivial problem↵
- [likes:8,option2] Easy problem↵
- [likes:8,option3] Average problem↵
- [likes:8,option4] Hard problem↵
- [likes:8,option5] Impossible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
[problem:2245D1]↵
↵
<spoiler summary="Solution">↵
[tutorial:2245D1] ↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
void solve() {↵
int n, m;↵
std::cin >> n >> m;↵
std::vector b(n, std::vector<int>(n));↵
while (m--) {↵
int o, i, j;↵
std::cin >> o >> i >> j;↵
i--;↵
j--;↵
b[i][j] = b[j][i] = o;↵
}↵
std::vector<std::vector<int>> g(n);↵
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {↵
if (b[i][i] == 1 && b[j][j] == 2) {↵
if (b[i][j] == 1) g[j].push_back(i);↵
else g[i].push_back(j);↵
}↵
}↵
std::vector<int> d(n), ans(n);↵
for (int u = 0; u < n; u++) for (auto v : g[u]) d[v]++;↵
int cnt = 0;↵
std::queue<int> q;↵
for (int u = 0; u < n; u++) if (!d[u]) q.push(u);↵
while (!q.empty()) {↵
int u = q.front();↵
q.pop();↵
if (b[u][u] == 1) ans[u] = ++cnt;↵
else ans[u] = -(++cnt);↵
for (auto v : g[u]) if (!--d[v]) q.push(v);↵
}↵
if (cnt == n) {↵
for (int i = 0; i < n; i++) for (int j = i; j < n; j++) {↵
if (b[i][j] == 1 && ans[i] + ans[j] < 0) return void(std::cout << "NO\n");↵
if (b[i][j] == 2 && ans[i] + ans[j] >= 0) return void(std::cout << "NO\n");↵
}↵
std::cout << "YES\n";↵
for (int i = 0; i < n; i++) std::cout << ans[i] << " \n"[i + 1 == n];↵
} else {↵
std::cout << "NO\n";↵
}↵
}↵
↵
int main() {↵
std::ios::sync_with_stdio(0);↵
std::cin.tie(0);↵
↵
int t;↵
std::cin >> t;↵
while (t--) solve();↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Quality">↵
↵
- [likes:9,option1] Excellent problem↵
- [likes:9,option2] Good problem↵
- [likes:9,option3] Average problem↵
- [likes:9,option4] Bad problem↵
- [likes:9,option5] Horrible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:10,option1] Trivial problem↵
- [likes:10,option2] Easy problem↵
- [likes:10,option3] Average problem↵
- [likes:10,option4] Hard problem↵
- [likes:10,option5] Impossible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
[problem:2245D2]↵
↵
<spoiler summary="Solution">↵
[tutorial:2245D2] ↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
void solve() {↵
int n, m;↵
std::cin >> n >> m;↵
std::vector d(2, std::vector<int>(n));↵
std::vector<std::vector<std::pair<int, int>>> g(n);↵
while (m--) {↵
int o, i, j;↵
std::cin >> o >> i >> j;↵
o--;↵
i--;↵
j--;↵
g[i].emplace_back(j, o);↵
g[j].emplace_back(i, o);↵
d[o][i]++;↵
d[o][j]++;↵
}↵
std::queue<int> q;↵
std::vector<bool> vis(n);↵
for (int i = 0; i < n; i++) if (d[0][i] == 0 || d[1][i] == 0) q.push(i), vis[i] = true;↵
std::vector<std::pair<int, int>> t;↵
while (!q.empty()) {↵
int u = q.front();↵
q.pop();↵
if (d[0][u] == 0) t.emplace_back(u, -1);↵
else t.emplace_back(u, 1);↵
for (auto [v, o] : g[u]) if (!--d[o][v] && !vis[v]) {↵
vis[v] = true;↵
q.push(v);↵
}↵
}↵
if (t.size() < n) return void(std::cout << "NO\n");↵
std::cout << "YES\n";↵
std::vector<int> ans(n);↵
std::reverse(t.begin(), t.end());↵
for (int i = 0; i < n; i++) ans[t[i].first] = (i + 1) * t[i].second;↵
for (int i = 0; i < n; i++) std::cout << ans[i] << " \n"[i + 1 == n];↵
}↵
↵
int main() {↵
std::ios::sync_with_stdio(0);↵
std::cin.tie(0);↵
↵
int t;↵
std::cin >> t;↵
while (t--) solve();↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Quality">↵
↵
- [likes:11,option1] Excellent problem↵
- [likes:11,option2] Good problem↵
- [likes:11,option3] Average problem↵
- [likes:11,option4] Bad problem↵
- [likes:11,option5] Horrible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:12,option1] Trivial problem↵
- [likes:12,option2] Easy problem↵
- [likes:12,option3] Average problem↵
- [likes:12,option4] Hard problem↵
- [likes:12,option5] Impossible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
[problem:2245E]↵
↵
<spoiler summary="Solution">↵
[tutorial:2245E] ↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
void solve() {↵
int n;↵
std::cin >> n;↵
std::vector<std::vector<int>> g(n);↵
for (int i = 0; i < n - 1; i++) {↵
int u, v;↵
std::cin >> u >> v;↵
u--;↵
v--;↵
g[u].push_back(v);↵
g[v].push_back(u);↵
}↵
std::vector<bool> vis(n);↵
long long ans = 0;↵
int c = 0;↵
auto dfs = [&](auto&& self, int u) -> void {↵
vis[u] = true;↵
for (auto v : g[u]) {↵
if (g[v].size() & 1) ans += c++;↵
else if (!vis[v]) self(self, v);↵
}↵
};↵
for (int u = 0; u < n; u++) if (~g[u].size() & 1 && !vis[u]) {↵
c = 0;↵
dfs(dfs, u);↵
}↵
for (int u = 0; u < n; u++) for (auto v : g[u]) if (v > u) ans += g[u].size() & g[v].size() & 1;↵
std::cout << ans << "\n";↵
}↵
↵
int main() {↵
std::ios::sync_with_stdio(0);↵
std::cin.tie(0);↵
↵
int t;↵
std::cin >> t;↵
while (t--) solve();↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Quality">↵
↵
- [likes:13,option1] Excellent problem↵
- [likes:13,option2] Good problem↵
- [likes:13,option3] Average problem↵
- [likes:13,option4] Bad problem↵
- [likes:13,option5] Horrible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:14,option1] Trivial problem↵
- [likes:14,option2] Easy problem↵
- [likes:14,option3] Average problem↵
- [likes:14,option4] Hard problem↵
- [likes:14,option5] Impossible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
[problem:2245F]↵
↵
<spoiler summary="Solution">↵
[tutorial:2245F] ↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
M = 998244353↵
N = 501↵
fac = [0] * N↵
fac[0] = 1↵
for i in range(1, N):↵
fac[i] = fac[i - 1] * i % M↵
inv = [0] * N↵
inv[-1] = pow(fac[-1], M - 2, M)↵
for i in range(N - 2, -1, -1):↵
inv[i] = inv[i + 1] * (i + 1) % M↵
def comb(n, k):↵
if k < 0 or k > n:↵
return 0↵
return fac[n] * inv[k] % M * inv[n - k] % M↵
↵
for _ in range(int(input())):↵
n = int(input())↵
a = list(map(int, input().split()))↵
if sum(max(0, v) for v in a) >= n:↵
print(0)↵
continue↵
a.append(-1)↵
f = [[[0] for _ in range(n)] for _ in range(n + 1)]↵
g = [[0] * n for _ in range(n + 1)]↵
for r in range(n):↵
if a[r + 1] != -1:↵
for l in range(n):↵
f[l][r] = [0] * (a[r + 1] + 1)↵
for i in range(1, n + 1):↵
f[i][i - 1][0] = 1↵
g[i][i - 1] = 1↵
def w(i, k):↵
if i == k:↵
return 1 if a[k] <= 0 else 0↵
else:↵
return f[i][k - 1][a[k]] if a[k] != -1 else g[i][k - 1]↵
for l in range(n - 1, -1, -1):↵
for r in range(l, n):↵
if a[r + 1] == -1:↵
for k in range(l, r + 1):↵
g[l][r] = (g[l][r] + comb(r - l, k - l) * w(l, k) % M * g[k + 1][r] % M) % M↵
else:↵
for c in range(1, a[r + 1] + 1):↵
for k in range(l, r + 1):↵
f[l][r][c] = (f[l][r][c] + comb(r - l, k - l) * w(l, k) % M * f[k + 1][r][c - 1] % M) % M↵
print(w(0, n))↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Quality">↵
↵
- [likes:15,option1] Excellent problem↵
- [likes:15,option2] Good problem↵
- [likes:15,option3] Average problem↵
- [likes:15,option4] Bad problem↵
- [likes:15,option5] Horrible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:16,option1] Trivial problem↵
- [likes:16,option2] Easy problem↵
- [likes:16,option3] Average problem↵
- [likes:16,option4] Hard problem↵
- [likes:16,option5] Impossible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
[problem:2245G]↵
↵
<spoiler summary="Solution">↵
[tutorial:2245G] ↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
std::string query(const std::vector<int>& a) {↵
std::cout << "? " << a.size();↵
for (auto v : a) std::cout << " " << v + 1;↵
std::cout << std::endl;↵
std::string s;↵
std::cin >> s;↵
return s;↵
}↵
↵
std::vector<int> work(const std::vector<int>& a, const std::vector<int>& b) {↵
if (a.empty() || b.empty()) return {};↵
std::vector<int> s;↵
for (auto v : a) s.push_back(v);↵
for (auto v : b) s.push_back(v);↵
std::string t = query(s);↵
std::vector<int> r;↵
for (int i = 0; i < b.size(); i++) if (t[i + a.size()] == '0') r.push_back(b[i]);↵
return r;↵
}↵
↵
void solve() {↵
int n;↵
std::cin >> n;↵
std::vector<std::vector<int>> g(n);↵
auto find = [&](auto&& self, std::vector<int> a, std::vector<int> b) -> void {↵
if (a.empty() || b.empty()) return;↵
if (a.size() == 1) {↵
for (auto v : b) g[v].push_back(a[0]), g[a[0]].push_back(v);↵
return;↵
}↵
int m = a.size() / 2;↵
std::vector a1(a.begin(), a.begin() + m), a2(a.begin() + m, a.end());↵
auto p1 = work(a1, b);↵
std::set<int> vis(p1.begin(), p1.end());↵
std::vector<int> nb, p2;↵
for (auto v : b) {↵
if (vis.count(v)) nb.push_back(v);↵
else p2.push_back(v);↵
}↵
self(self, a1, p1);↵
for (auto v : work(a2, nb)) p2.push_back(v);↵
self(self, a2, p2);↵
};↵
auto dfs = [&](auto&& self, std::vector<int> a) -> void {↵
if (a.size() <= 1) return;↵
std::string t = query(a);↵
std::vector<int> p1, p2;↵
for (int i = 0; i < a.size(); i++) {↵
if (t[i] == '0') p2.push_back(a[i]);↵
else p1.push_back(a[i]);↵
}↵
self(self, p2);↵
std::vector<int> col(n, -1);↵
std::vector<std::vector<int>> b(2);↵
for (auto w : p2) if (col[w] == -1) {↵
std::queue<int> q;↵
q.push(w);↵
col[w] = 0;↵
while (!q.empty()) {↵
int u = q.front();↵
q.pop();↵
b[col[u]].push_back(u);↵
for (auto v : g[u]) if (col[v] == -1) {↵
col[v] = col[u] ^ 1;↵
q.push(v);↵
}↵
}↵
}↵
for (int i = 0; i < 2; i++) {↵
find(find, b[i], work(b[i], p1));↵
}↵
};↵
std::vector<int> a(n);↵
std::iota(a.begin(), a.end(), 0);↵
dfs(dfs, a);↵
std::cout << "!" << std::endl;↵
for (int u = 0; u < n; u++) for (auto v : g[u]) if (v > u) std::cout << u + 1 << " " << v + 1 << std::endl;↵
}↵
↵
int main() {↵
std::ios::sync_with_stdio(0);↵
std::cin.tie(0);↵
↵
int t;↵
std::cin >> t;↵
while (t--) solve();↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Quality">↵
↵
- [likes:17,option1] Excellent problem↵
- [likes:17,option2] Good problem↵
- [likes:17,option3] Average problem↵
- [likes:17,option4] Bad problem↵
- [likes:17,option5] Horrible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:18,option1] Trivial problem↵
- [likes:18,option2] Easy problem↵
- [likes:18,option3] Average problem↵
- [likes:18,option4] Hard problem↵
- [likes:18,option5] Impossible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
[problem:2245H]↵
↵
<spoiler summary="Solution">↵
Tutorial will be added after the first official solve.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Quality">↵
↵
- [likes:19,option1] Excellent problem↵
- [likes:19,option2] Good problem↵
- [likes:19,option3] Average problem↵
- [likes:19,option4] Bad problem↵
- [likes:19,option5] Horrible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:20,option1] Trivial problem↵
- [likes:20,option2] Easy problem↵
- [likes:20,option3] Average problem↵
- [likes:20,option4] Hard problem↵
- [likes:20,option5] Impossible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
