### vovuh's blog

By vovuh, history, 3 months ago,

1454A - Special Permutation

Idea: MikeMirzayanov

Tutorial
Solution
#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cout << (i + 1) % n + 1 << " ";
}
cout << endl;
}

return 0;
}


1454B - Unique Bid Auction

Idea: MikeMirzayanov

Tutorial
Solution
#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> cnt(n + 1), idx(n + 1);
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
++cnt[x];
idx[x] = i + 1;
}
int ans = -1;
for (int i = 0; i <= n; ++i) {
if (cnt[i] == 1) {
ans = idx[i];
break;
}
}
cout << ans << endl;
}

return 0;
}


1454C - Sequence Transformation

Idea: MikeMirzayanov

Tutorial
Solution
#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (auto &it : a) cin >> it;
vector<int> res(n + 1, 1);
n = unique(a.begin(), a.end()) - a.begin();
a.resize(n);
for (int i = 0; i < n; ++i) {
res[a[i]] += 1;
}
res[a[0]] -= 1;
res[a[n - 1]] -= 1;
int ans = 1e9;
for (int i = 0; i < n; ++i) {
ans = min(ans, res[a[i]]);
}
cout << ans << endl;
}

return 0;
}


1454D - Number into Sequence

Idea: MikeMirzayanov

Tutorial
Solution
#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

int t;
cin >> t;
while (t--) {
long long n;
cin >> n;

vector<pair<int, long long>> val;
for (long long i = 2; i * i <= n; ++i) {
int cnt = 0;
while (n % i == 0) {
++cnt;
n /= i;
}
if (cnt > 0) {
val.push_back({cnt, i});
}
}
if (n > 1) {
val.push_back({1, n});
}

sort(val.rbegin(), val.rend());
vector<long long> ans(val[0].first, val[0].second);
for (int i = 1; i < int(val.size()); ++i) {
for (int j = 0; j < val[i].first; ++j) {
ans.back() *= val[i].second;
}
}

cout << ans.size() << endl;
for (auto it : ans) cout << it << " ";
cout << endl;
}

return 0;
}


1454E - Number of Simple Paths

Idea: vovuh

Tutorial
Solution
#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<set<int>> g(n);
for (int i = 0; i < n; ++i) {
int x, y;
cin >> x >> y;
--x, --y;
g[x].insert(y);
g[y].insert(x);
}
vector<int> val(n, 1);
queue<int> leafs;
for (int i = 0; i < n; ++i) {
if (g[i].size() == 1) {
leafs.push(i);
}
}
while (!leafs.empty()) {
int v = leafs.front();
leafs.pop();
int to = *g[v].begin();
val[to] += val[v];
val[v] = 0;
g[v].clear();
g[to].erase(v);
if (g[to].size() == 1) {
leafs.push(to);
}
}
long long ans = 0;
for (int i = 0; i < n; ++i) {
ans += val[i] * 1ll * (val[i] - 1) / 2;
ans += val[i] * 1ll * (n - val[i]);
}
cout << ans << endl;
}

return 0;
}


1454F - Array Partition

Idea: MikeMirzayanov

Tutorial
Solution
#include <bits/stdc++.h>

using namespace std;

bool found;

void shift(multiset<int> &l, multiset<int> &r, int val) {
l.erase(l.find(val));
r.insert(val);
}

void check(const multiset<int> &lf, const multiset<int> &mid, const multiset<int> &rg) {
if (found || lf.empty() || mid.empty() || rg.empty()) {
return;
}
if (*lf.rbegin() == *mid.begin() && *mid.begin() == *rg.rbegin()) {
found = true;
cout << "YES" << endl;
cout << lf.size() << " " << mid.size() << " " << rg.size() << endl;
}
}

int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (auto &it : a) cin >> it;

found = false;
multiset<int> lf, mid(a.begin(), a.end()), rg;
int r = n - 1;
for (int l = 0; l < n - 2; ++l) {
shift(mid, lf, a[l]);
while (r - 1 >= l && a[r] <= *lf.rbegin()) {
shift(mid, rg, a[r]);
--r;
}

while (r - 1 < l) {
shift(rg, mid, a[r + 1]);
++r;
}

check(lf, mid, rg);

shift(lf, mid, a[l]);
check(lf, mid, rg);
shift(mid, lf, a[l]);

if (rg.empty()) continue;

shift(rg, mid, a[r + 1]);
check(lf, mid, rg);
shift(mid, rg, a[r + 1]);
}
if (!found) {
cout << "NO" << endl;
}
}

return 0;
}

Solution (Gassa)
// Author: Ivan Kazmenko (gassa@mail.ru)
module solution;
import std.algorithm;
import std.conv;
import std.range;
import std.stdio;
import std.string;

void main ()
{
foreach (test; 0..tests)
{
auto a = readln.splitter.map !(to !(int)).array;
auto x = a.dup;
foreach (i; 1..n)
{
x[i] = max (x[i], x[i - 1]);
}
auto y = a.dup;
foreach_reverse (i; 0..n - 1)
{
y[i] = max (y[i], y[i + 1]);
}

auto v = a.maxElement;
auto maxPlaces = n.iota.filter !(i => a[i] == v).array;
int lo = maxPlaces[\$ / 2];
int hi = lo + 1;

while (true)
{
if (lo == 0 || hi == n)
{
writeln ("NO");
break;
}
if (x[lo - 1] == v && y[hi] == v)
{
writeln ("YES");
writeln (lo, " ", hi - lo, " ", n - hi);
break;
}
int u = (lo - 1 == 0) ? int.min :
min (x[lo - 2], a[lo - 1]);
int w = (hi + 1 >= n) ? int.min :
min (y[hi + 1], a[hi]);
if (u > w)
{
v = min (v, a[lo - 1]);
lo -= 1;
}
else
{
v = min (v, a[hi]);
hi += 1;
}
}
}
}


• +134

By vovuh, history, 3 months ago, translation,

Hello! Codeforces Round #686 (Div. 3) will start at Nov/24/2020 17:35 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 (or 8) problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

• take part in at least two rated rounds (and solve at least one problem in each of them),
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Daria nooinenoojno Stepanova, Mikhail awoo Piklyaev, Maksim Neon Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round. Also thanks to Artem Rox Plotkin and Dmitrii _overrated_ Umnov for the discussion of ideas and testing the round!

Good luck!

UPD: I would also like to thank Ivan Gassa Kazmenko for invaluable help with the round preparation!

UPD2: Editorial is published!

• +402

By vovuh, history, 4 months ago,

I'm really sorry about issues with problems E and F. Can't say anything more because I don't want to justify my mistakes.

1433A - Boring Apartments

Idea: vovuh

Tutorial
Solution

1433B - Yet Another Bookshelf

Idea: vovuh

Tutorial
Solution

1433C - Dominant Piranha

Idea: vovuh

Tutorial
Solution

1433D - Districts Connection

Idea: MikeMirzayanov

Tutorial
Solution

1433E - Two Round Dances

Idea: MikeMirzayanov

Tutorial
Solution

1433F - Zero Remainder Sum

Idea: MikeMirzayanov

Tutorial
Solution

1433G - Reducing Delivery Cost

Idea: MikeMirzayanov

Tutorial
Solution

• +115

By vovuh, history, 4 months ago,

Alright, I'm done. I wanted to write a blog like that for a long time, but now I really don't have enough patience to ignore this issue anymore. I want to say that I get 100-200 clarifications each Div.3 round. It doesn't even matter how well the statements are, it doesn't matter if there are any issues with solutions or checkers, people always find what to ask.

Before I start whining here, I really want to recommend anyone to read these two Um_nik blogs: this one and this one. Sorry, Um_nik, I unnecessarily tagged you, I will not do that anymore.

Now some breaking news for most participants: your local IDE compiler and Codeforces compiler are actually different things! If your code works fine locally but gets WA/TL/RE/ML/etc on Codeforces, it (most probably) means you have a bug somewhere in your code. There are rare cases when the issue is with compiler differences, but these cases are really rare. If you have such issue, what do you think you have to do? Of course write a question about that! I got like 50 questions like this on today's contest. It's hilarious. I really suggest you to run your code in custom invocation tab instead of writing a question. If you run your code on Codeforces, you will get the output as it is here and, probably, you will understand what is wrong with your solution.

Also, I got a lot of questions about the problem 1433F - Zero Remainder Sum . Many people were confused if the whole sum you get should be divisible by $k$ or the sum of each row should be divisible by $k$. The thing I want to recommend here: read Um_nik blogs. Whoops, unnecessary tag, sorry. To be fair, you could maybe... probably... at least read and understand the first example and the Note about that (the matrix of size $3 \times 4$, $12$ elements, come on, it is not hard). If you read that, you will understand that the whole sum should be divisible by $k$, because otherwise the example answer is wrong. There were no sentences showing that you should consider the divisibility of each row. I make Notes section exactly for such cases (when something can be misleading or unclear). I'm also trying to make examples as clear as possible, to try to cover every possible case that can confuse anyone (this problem was not an exception).

The thing about clarifications that really makes me burn: why do you think that your question should be answered immediately after you send it? The answer time here is not more than $5$ minutes usually. I heard that the answer time on other platforms can be much and much more than here. Also, please, take in consideration that Codeforces is a huge platform and there are almost 17 thousands participants in the today's round. 17 thousands people versus me and sometimes, maybe, MikeMirzayanov, BledDest or someone else who helps me with questions. When you are spamming something like "why my question is not answered?? please answer!!" you are just increasing the amount of work for me and the waiting time for others. I always answer all questions, you just need to be a bit patient.

About the problem 1433E - Two Round Dances. Yeah, the statement of this problem was really misleading and didn't match the examples, and I'm really sorry about that. We added this problem like $2-3$ hours before the round start just to smooth out the difficulty curve. This is pretty old problem that was already partially prepared. I read the statement, wrote the solution and it matched my understanding of the problem. I wanted to write proving naive solution a bit later, but I had too many things to correct in other problems' statements, so I completely forgot to do that. Sorry for that issue, this was my fault.

Continuing the previous paragraph, I want to mention two people (without their handles, it will be obvious to them even without direct mentioning): one guy wrote that "this round is complete disaster make it unrated". I opened his submissions list and saw he solved only A and B. The only thing that could make this round unrated is the wrong statement of E. He didn't even solve C and D. I asked him if the issue with E really affected him when he didn't solve easier problems, but got no answer. The other guy was really rude, and he flamed so much. As the last question from him, I got "what the hell is this there is no mention of rotation in the question. do you realize that?? give you handle i will talk to u later" (this is a citation). I'm really sad about that. I don't understand why some people think they can just talk like that to others.

Some things about previous rounds: one day, I got so many questions if the round is rated or not during the time we were figuring out if we really have to make it unrated. I got something like $50$ questions about this and just answered "read the global announcement". $50$ times. I wasted like $5$ minutes to answer all such questions instead of answering the real ones.

About English: so many questions have pretty strange English and I just can't understand what are you trying to say/ask. Please, try to make your question as clear as possible, because if you just write some sequence of words and send it to me, I will answer "question in unclear" (after spending like $30$ seconds trying to understand that) and will wait for the real question instead of the sequence of words without meaning.

And, in conclusion, I want to recommend you: read Um_nik blogs (whoops). He did really great work about how to read and not to read problem statements. These blogs are a high quality source of understanding how to read and understand statements. Please, read the statement, read the Note, try to figure out the answer on the example, read the global announcement before asking the question. Much question answers can be retrieved from these things. I'm exhausted because of answering questions that are answered in the problem itself (the great example is today's problem C. I got like $10-20$ questions like "can there be several answers???" but it was bolded in the statement).

I'm done. Thank you for reading if you had patience to read all my whining. Feel free to blame me or something like that, I understand that I'm not perfect and make a lot of mistakes.

• +979

By vovuh, history, 4 months ago, translation,

Hello! Codeforces Round #677 (Div. 3) will start at Oct/20/2020 17:35 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 (or 8) problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

• take part in at least two rated rounds (and solve at least one problem in each of them),
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Daria nooinenoojno Stepanova, Mikhail awoo Piklyaev, Maksim Neon Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round. Also thanks to Artem Rox Plotkin and Dmitrii _overrated_ Umnov for the discussion of ideas and testing the round!

Good luck!

UPD: Thanks to infinitepro, nuipojaluista, MrReDoX and Peinot for testing the round and giving the feedback about the problems!

UPD2: Editorial is published!

• +271

By vovuh, history, 5 months ago,

1426A - Floor Number

Idea: fcspartakm

Tutorial
Solution

1426B - Symmetric Matrix

Idea: BledDest

Tutorial
Solution

1426C - Increase and Copy

Idea: vovuh

Tutorial
Solution
Solution 2

1426D - Non-zero Segments

Idea: BledDest

Tutorial
Solution

1426E - Rock, Paper, Scissors

Idea: fcspartakm

Tutorial
Solution

1426F - Number of Subsequences

Idea: fcspartakm

Tutorial
Solution

• +102

By vovuh, history, 5 months ago,

Notice the unusual start time.

Hello!

Codeforces Round #674 (Div. 3) will start at Sep/28/2020 11:05 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

This round consists mostly of the problems of the first stage of All-Russian Olympiad of School Students in Saratov and will be hosted during the real competition time. The problems were invented and prepared by Ivan BledDest Androsov, Alexander fcspartakm Frolov and me.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 (or 8) problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

• take part in at least two rated rounds (and solve at least one problem in each of them),
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Daria nooinenoojno Stepanova, Mikhail awoo Piklyaev, Maksim Neon Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round. Also thanks to Artem Rox Plotkin and Dmitrii _overrated_ Umnov for the discussion of ideas and testing the round!

Good luck!

UPD: Thanks to Ivan MrReDoX Ushakov, Ivan Ivan19981305 Georgiev and Dmitry nuipojaluista Kadomtsev for testing the round!

UPD2: Editorial is published!

• +258

By vovuh, history, 6 months ago,

I'm so thankful to all testers, especially to Gassa and Rox for their invaluable help!

1409A - Yet Another Two Integers Problem

Idea: vovuh

Tutorial
Solution

1409B - Minimum Product

Idea: vovuh

Tutorial
Solution

1409C - Yet Another Array Restoration

Idea: vovuh

Tutorial
Solution (Gassa)
Solution (vovuh)
Solution (Rox)

1409D - Decrease the Sum of Digits

Idea: MikeMirzayanov

Tutorial
Solution

1409E - Two Platforms

Idea: vovuh

Tutorial
Solution

1409F - Subsequences of Length Two

Idea: vovuh

Tutorial
Solution
Solution (Gassa, greedy, O(n^4))

• +107

By vovuh, history, 6 months ago, translation,

Hello! Codeforces Round #667 (Div. 3) will start at Sep/04/2020 17:35 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 (or 8) problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

• take part in at least two rated rounds (and solve at least one problem in each of them),
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Daria nooinenoojno Stepanova, Mikhail awoo Piklyaev, Maksim Neon Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round. Also thanks to Artem Rox Plotkin and Dmitrii _overrated_ Umnov for the discussion of ideas and testing the round!

Good luck!

UPD: Huge thanks to Ivan Gassa Kazmenko for testing the round and fixing some issues with statements and the round in general! Also thanks to nuipojaluista, kocko, Ilya-bar and infinitepro for testing the round!

UPD2: Editorial is published!

• +365

By vovuh, history, 7 months ago,

All ideas belong to MikeMirzayanov.

1399A - Remove Smallest

Tutorial
Solution
#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (auto &it : a) cin >> it;
sort(a.begin(), a.end());
bool ok = true;
for (int i = 1; i < n; ++i) {
ok &= (a[i] - a[i - 1] <= 1);
}
if (ok) cout << "YES" << endl;
else cout << "NO" << endl;
}

return 0;
}


Tutorial
Solution
#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n), b(n);
for (auto &it : a) cin >> it;
for (auto &it : b) cin >> it;
int mna = *min_element(a.begin(), a.end());
int mnb = *min_element(b.begin(), b.end());
long long ans = 0;
for (int i = 0; i < n; ++i) {
ans += max(a[i] - mna, b[i] - mnb);
}
cout << ans << endl;
}

return 0;
}


1399C - Boats Competition

Tutorial
Solution
#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> cnt(n + 1);
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
++cnt[x];
}
int ans = 0;
for (int s = 2; s <= 2 * n; ++s) {
int cur = 0;
for (int i = 1; i < (s + 1) / 2; ++i) {
if (s - i > n) continue;
cur += min(cnt[i], cnt[s - i]);
}
if (s % 2 == 0) cur += cnt[s / 2] / 2;
ans = max(ans, cur);
}
cout << ans << endl;
}

return 0;
}


1399D - Binary String To Subsequences

Tutorial
Solution
#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

int t;
cin >> t;
while (t--) {
int n;
string s;
cin >> n >> s;
vector<int> ans(n);
vector<int> pos0, pos1;
for (int i = 0; i < n; ++i) {
int newpos = pos0.size() + pos1.size();
if (s[i] == '0') {
if (pos1.empty()) {
pos0.push_back(newpos);
} else {
newpos = pos1.back();
pos1.pop_back();
pos0.push_back(newpos);
}
} else {
if (pos0.empty()) {
pos1.push_back(newpos);
} else {
newpos = pos0.back();
pos0.pop_back();
pos1.push_back(newpos);
}
}
ans[i] = newpos;
}
cout << pos0.size() + pos1.size() << endl;
for (auto it : ans) cout << it + 1 << " ";
cout << endl;
}

return 0;
}


1399E1 - Weights Division (easy version)

Tutorial
Solution
#include <bits/stdc++.h>

using namespace std;

vector<int> w, cnt;
vector<vector<pair<int, int>>> g;

long long getdiff(int i) {
return w[i] * 1ll * cnt[i] - (w[i] / 2) * 1ll * cnt[i];
}

void dfs(int v, int p = -1) {
if (g[v].size() == 1) cnt[p] = 1;
for (auto [to, id] : g[v]) {
if (id == p) continue;
dfs(to, id);
if (p != -1) cnt[p] += cnt[id];
}
}

int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

int t;
cin >> t;
while (t--) {
int n;
long long s;
cin >> n >> s;
w = cnt = vector<int>(n - 1);
g = vector<vector<pair<int, int>>>(n);
for (int i = 0; i < n - 1; ++i) {
int x, y;
cin >> x >> y >> w[i];
--x, --y;
g[x].push_back({y, i});
g[y].push_back({x, i});
}
dfs(0);
set<pair<long long, int>> st;
long long cur = 0;
for (int i = 0; i < n - 1; ++i) {
st.insert({getdiff(i), i});
cur += w[i] * 1ll * cnt[i];
}
cerr << cur << endl;
int ans = 0;
while (cur > s) {
int id = st.rbegin()->second;
st.erase(prev(st.end()));
cur -= getdiff(id);
w[id] /= 2;
st.insert({getdiff(id), id});
++ans;
}
cout << ans << endl;
}

return 0;
}


1399E2 - Weights Division (hard version)

Tutorial
Solution
#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;

int n;
vector<int> w, c, cnt;
vector<vector<pair<int, int>>> g;

long long getdiff(int i) {
return w[i] * 1ll * cnt[i] - (w[i] / 2) * 1ll * cnt[i];
}

void dfs(int v, int p = -1) {
if (g[v].size() == 1) cnt[p] = 1;
for (auto [to, id] : g[v]) {
if (id == p) continue;
dfs(to, id);
if (p != -1) cnt[p] += cnt[id];
}
}

vector<long long> get(int clr) {
set<pair<long long, int>> st;
long long cur = 0;
for (int i = 0; i < n - 1; ++i) {
if (c[i] == clr) {
st.insert({getdiff(i), i});
cur += w[i] * 1ll * cnt[i];
}
}
vector<long long> res;
res.push_back(cur);
while (cur > 0 && !st.empty()) {
int id = st.rbegin()->second;
st.erase(prev(st.end()));
cur -= getdiff(id);
res.push_back(cur);
w[id] /= 2;
st.insert({getdiff(id), id});
}
return res;
}

int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

int t;
cin >> t;
while (t--) {
long long s;
cin >> n >> s;
w = c = cnt = vector<int>(n - 1);
g = vector<vector<pair<int, int>>>(n);
for (int i = 0; i < n - 1; ++i) {
int x, y;
cin >> x >> y >> w[i] >> c[i];
--x, --y;
g[x].push_back({y, i});
g[y].push_back({x, i});
}
dfs(0);
vector<long long> v1 = get(1), v2 = get(2);
int pos = int(v2.size()) - 1;
int ans = INF;
for (int i = 0; i < int(v1.size()); ++i) {
while (pos > 0 && v1[i] + v2[pos - 1] <= s) --pos;
if (v1[i] + v2[pos] <= s) {
ans = min(ans, i + pos * 2);
}
}
cout << ans << endl;
}

return 0;
}


1399F - Yet Another Segments Subset

Tutorial
Solution
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> rg;
vector<vector<int>> dp;

int calc(int l, int r) {
if (dp[l][r] != -1) return dp[l][r];
dp[l][r] = 0;
if (l > r) return dp[l][r];
bool add = count(rg[l].begin(), rg[l].end(), r); // can't be greater than 1
dp[l][r] = max(dp[l][r], add + (l + 1 > r ? 0 : calc(l + 1, r)));
for (auto nr : rg[l]) {
if (nr >= r) continue;
dp[l][r] = max(dp[l][r], add + calc(l, nr) + (nr + 1 > r ? 0 : calc(nr + 1, r)));
}
return dp[l][r];
}

int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> l(n), r(n);
vector<int> val;
for (int i = 0; i < n; ++i) {
cin >> l[i] >> r[i];
val.push_back(l[i]);
val.push_back(r[i]);
}
sort(val.begin(), val.end());
val.resize(unique(val.begin(), val.end()) - val.begin());
for (int i = 0; i < n; ++i) {
l[i] = lower_bound(val.begin(), val.end(), l[i]) - val.begin();
r[i] = lower_bound(val.begin(), val.end(), r[i]) - val.begin();
}
int siz = val.size();
dp = vector<vector<int>>(siz, vector<int>(siz, -1));
rg = vector<vector<int>>(siz);
for (int i = 0; i < n; ++i) {
rg[l[i]].push_back(r[i]);
}
cout << calc(0, siz - 1) << endl;
}

return 0;
}


• +124

By vovuh, history, 7 months ago, translation,

Hello! Codeforces Round #661 (Div. 3) will start at Aug/05/2020 17:35 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 (or 8) problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

• take part in at least two rated rounds (and solve at least one problem in each of them),
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Daria nooinenoojno Stepanova, Mikhail awoo Piklyaev, Maksim Neon Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round. Also thanks to Artem Rox Plotkin and Dmitrii _overrated_ Umnov for the discussion of ideas and testing the round!

Good luck!

UPD: Huge thanks to Ivan Gassa Kazmenko for testing the round and fixing some issues with statements and the round in general!

UPD2: Editorial is published!

• +424

By vovuh, history, 7 months ago,

All ideas belong to MikeMirzayanov.

1385A - Three Pairwise Maximums

Tutorial
Solution

1385B - Restore the Permutation by Merger

Tutorial
Solution

1385C - Make It Good

Tutorial
Solution

1385D - a-Good String

Tutorial
Solution

1385E - Directing Edges

Tutorial
Solution

1385F - Removing Leaves

Tutorial
Solution

1385G - Columns Swaps

Tutorial
Solution

• +157

By vovuh, history, 7 months ago, translation,

Hello! Codeforces Round #656 (Div. 3) will start at Jul/17/2020 17:35 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 (or 8) problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

• take part in at least two rated rounds (and solve at least one problem in each of them),
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Daria nooinenoojno Stepanova, Mikhail awoo Piklyaev, Maksim Neon Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round. Also thanks to Artem Rox Plotkin and Dmitrii _overrated_ Umnov for the discussion of ideas and testing the round!

Good luck!

UPD: Also thanks to infinitepro for help with statements and testing the round!

UPD2: Editorial is published!

• +511

By vovuh, history, 8 months ago,

1374A - Required Remainder

Idea: vovuh

Tutorial
Solution

1374B - Multiply by 2, divide by 6

Idea: vovuh

Tutorial
Solution

1374C - Move Brackets

Idea: MikeMirzayanov

Tutorial
Solution

1374D - Zero Remainder Array

Idea: vovuh

Tutorial
Solution

1374E1 - Reading Books (easy version)

Idea: MikeMirzayanov

Tutorial
Solution

1374E2 - Reading Books (hard version)

Idea: MikeMirzayanov

Tutorial
Solution

1374F - Cyclic Shifts Sorting

Idea: MikeMirzayanov

Tutorial
Solution

• +92

By vovuh, history, 8 months ago, translation,

<almost-copy-pasted-part>

Hello! Codeforces Round #653 (Div. 3) will start at Jun/28/2020 17:35 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 (or 8) problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

• take part in at least two rated rounds (and solve at least one problem in each of them),
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Daria nooinenoojno Stepanova, Mikhail awoo Piklyaev, Maksim Neon Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round. Also thanks to Artem Rox Plotkin and Dmitrii _overrated_ Umnov for the discussion of ideas and testing the round!

Good luck!

</almost-copy-pasted-part>

UPD: Also thanks to ma_da_fa_ka for testing the round and special thanks to Dmitrii _overrated_ Umnov, Artem Rox Plotkin and, of course, Mike MikeMirzayanov Mirzayanov for discussing ideas and great help with round preparaion!

UPD2: Editorial is published!

• +450

By vovuh, history, 9 months ago,

All problems, except the problem D, are mine. The problem D author is MikeMirzayanov.

1353A - Most Unstable Array

Tutorial
Solution

1353B - Two Arrays And Swaps

Tutorial
Solution

1353C - Board Moves

Tutorial
Solution

1353D - Constructing the Array

Tutorial
Solution

1353E - K-periodic Garland

Tutorial
Solution

1353F - Decreasing Heights

Tutorial
Solution

• +150

By vovuh, history, 9 months ago,

<almost-copy-pasted-part>

Hello! Codeforces Round #642 (Div. 3) will start at May/14/2020 17:35 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 (or 8) problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

• take part in at least two rated rounds (and solve at least one problem in each of them),
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Daria nooinenoojno Stepanova, Mikhail awoo Piklyaev, Maksim Neon Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round. Also thanks to Artem Rox Plotkin and Dmitrii _overrated_ Umnov for the discussion of ideas and testing the round!

Good luck!

</almost-copy-pasted-part>

UPD: Thanks to ma_da_fa_ka, Jaydeep999997, abhishek_saini, infinitepro and socho for testing the round!

UPD2: Editorial is published!

• +397

By vovuh, history, 10 months ago,

All problem ideas belong to MikeMirzayanov. And he prepared all problems himself. I just helped with testing, reviewing and tutorial writing.

1352A - Sum of Round Numbers

Tutorial
Solution

1352B - Same Parity Summands

Tutorial
Solution

1352C - K-th Not Divisible by n

Tutorial
Solution

1352D - Alice, Bob and Candies

Tutorial
Solution in O(n)
Solution in O(n^2)

1352E - Special Elements

Tutorial
Solution

1352F - Binary String Reconstruction

Tutorial
Solution

1352G - Special Permutation

Tutorial
Solution

• +133

By vovuh, history, 10 months ago,

1343A - Candies

Idea: vovuh

Tutorial
Solution

1343B - Balanced Array

Idea: vovuh

Tutorial
Solution

1343C - Alternating Subsequence

Idea: vovuh and MikeMirzayanov

Tutorial
Solution

1343D - Constant Palindrome Sum

Idea: MikeMirzayanov

Tutorial
Solution

1343E - Weights Distributing

Idea: MikeMirzayanov

Tutorial
Solution

1343F - Restore the Permutation by Sorted Segments

Idea: MikeMirzayanov

Tutorial
Solution

• +163

By vovuh, history, 10 months ago, translation,

<almost-copy-pasted-part>

Hello! Codeforces Round #636 (Div. 3) will start at Apr/21/2020 17:35 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 (or 8) problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

• take part in at least two rated rounds (and solve at least one problem in each of them),
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Daria nooinenoojno Stepanova, Mikhail awoo Piklyaev, Maksim Neon Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round. Also thanks to Artem Rox Plotkin and Dmitrii _overrated_ Umnov for the discussion of ideas and testing the round!

Good luck!

</almost-copy-pasted-part>

UPD: Also thanks to Sakhiya07, infinitepro and ma_da_fa_ka for testing the round!

UPD2: Editorial is published!

• +297

By vovuh, history, 10 months ago,

1335A - Candies and Two Sisters

Idea: vovuh

Tutorial
Solution

1335B - Construct the String

Idea: MikeMirzayanov

Tutorial
Solution

1335C - Two Teams Composing

Idea: MikeMirzayanov

Tutorial
Solution

1335D - Anti-Sudoku

Idea: vovuh

Tutorial
Solution

1335E1 - Three Blocks Palindrome (easy version)

Idea: MikeMirzayanov

Tutorial
Solution

1335E2 - Three Blocks Palindrome (hard version)

Idea: MikeMirzayanov

Tutorial
Solution

1335F - Robots on a Grid

Idea: MikeMirzayanov

Tutorial
Solution
Solution (actually _overrated_, fastest O(nm log nm))

• +115

By vovuh, history, 10 months ago,

<almost-copy-pasted-part>

Hello! Codeforces Round #634 (Div. 3) will start at Apr/13/2020 17:35 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 (or 8) problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

• take part in at least two rated rounds (and solve at least one problem in each of them),
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Daria nooinenoojno Stepanova, Mikhail awoo Piklyaev, Maksim Neon Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round. Also thanks to Artem Rox Plotkin and Dmitrii _overrated_ Umnov for the discussion of ideas and testing the round!

Good luck!

</almost-copy-pasted-part>

UPD: Also thanks to ma_da_fa_ka and infinitepro for testing the round!

UPD2: Editorial is published!

• +358

By vovuh, history, 11 months ago,

1328A - Divisibility Problem

Idea: MikeMirzayanov

Tutorial
Solution

1328B - K-th Beautiful String

Idea: MikeMirzayanov

Tutorial
Solution

1328C - Ternary XOR

Idea: vovuh

Tutorial
Solution

1328D - Carousel

Idea: MikeMirzayanov

Tutorial
Solution

1328E - Tree Queries

Idea: MikeMirzayanov and vovuh

Tutorial
Solution

1328F - Make k Equal

Idea: MikeMirzayanov

Tutorial
Solution

• +127

By vovuh, history, 11 months ago, translation,

<almost-copy-pasted-part>

Hello! Codeforces Round #629 (Div. 3) will start at Mar/26/2020 17:35 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 (or 8) problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

• take part in at least two rated rounds (and solve at least one problem in each of them),
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Daria nooinenoojno Stepanova, Mikhail awoo Piklyaev, Maksim Neon Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

</almost-copy-pasted-part>

Thanks to Artem Rox Plotkin and Dmitrii _overrated_ Umnov for help with testing the round!

UPD: Also thanks to Vitaliy kuviman Kudasov for testing the round!

UPD2: Editorial is published!

• +352

By vovuh, history, 12 months ago,

Suddendly, all ideas of this contest are mine. And I'm very sorry about one missing small test in the problem B. This is the biggest mistake I made during the preparation of this round.

1324A - Yet Another Tetris Problem

Tutorial
Solution
for i in range(int(input())):
n = int(input())
cnto = sum(list(map(lambda x: int(x) % 2, input().split())))
print('YES' if cnto == 0 or cnto == n else 'NO')


1324B - Yet Another Palindrome Problem

Tutorial
Solution
for i in range(int(input())):
n = int(input())
s = list(map(int, input().split()))
ok = False
for i in range(n):
for j in range(i + 2, n):
if s[i] == s[j]: ok = True
print('YES' if ok else 'NO')


1324C - Frog Jumps

Tutorial
Solution
#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

int t;
cin >> t;
while (t--) {
string s;
cin >> s;
vector<int> pos;
pos.push_back(0);
for (int i = 0; i < int(s.size()); ++i) {
if (s[i] == 'R') pos.push_back(i + 1);
}
pos.push_back(s.size() + 1);
int ans = 0;
for (int i = 0; i < int(pos.size()) - 1; ++i) {
ans = max(ans, pos[i + 1] - pos[i]);
}
cout << ans << endl;
}

return 0;
}


1324D - Pair of Topics

Tutorial
Solution
#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

int n;
cin >> n;
vector<int> a(n), b(n);
for (auto &it : a) cin >> it;
for (auto &it : b) cin >> it;
vector<int> c(n);
for (int i = 0; i < n; ++i) {
c[i] = a[i] - b[i];
}
sort(c.begin(), c.end());

long long ans = 0;
for (int i = 0; i < n; ++i) {
if (c[i] <= 0) continue;
int pos = lower_bound(c.begin(), c.end(), -c[i] + 1) - c.begin();
ans += i - pos;
}

cout << ans << endl;

return 0;
}


1324E - Sleeping Schedule

Tutorial
Solution
#include <bits/stdc++.h>

using namespace std;

bool in(int x, int l, int r) {
return l <= x && x <= r;
}

int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

int n, h, l, r;
cin >> n >> h >> l >> r;
vector<int> a(n);
for (auto &it : a) cin >> it;
vector<vector<int>> dp(n + 1, vector<int>(n + 1, INT_MIN));
dp[0][0] = 0;
int sum = 0;
for (int i = 0; i < n; ++i) {
sum += a[i];
for (int j = 0; j <= n; ++j) {
dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + in((sum - j) % h, l, r));
if (j < n) dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + in((sum - j - 1) % h, l, r));
}
}

cout << *max_element(dp[n].begin(), dp[n].end()) << endl;

return 0;
}


1324F - Maximum White Subtree

Tutorial
Solution
#include <bits/stdc++.h>

using namespace std;

vector<int> a;
vector<int> dp;
vector<int> ans;
vector<vector<int>> g;

void dfs(int v, int p = -1) {
dp[v] = a[v];
for (auto to : g[v]) {
if (to == p) continue;
dfs(to, v);
dp[v] += max(dp[to], 0);
}
}

void dfs2(int v, int p = -1) {
ans[v] = dp[v];
for (auto to : g[v]) {
if (to == p) continue;
dp[v] -= max(0, dp[to]);
dp[to] += max(0, dp[v]);
dfs2(to, v);
dp[to] -= max(0, dp[v]);
dp[v] += max(0, dp[to]);
}
}

int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

int n;
cin >> n;
a = dp = ans = vector<int>(n);
g = vector<vector<int>>(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
if (a[i] == 0) a[i] = -1;
}
for (int i = 0; i < n - 1; ++i) {
int x, y;
cin >> x >> y;
--x, --y;
g[x].push_back(y);
g[y].push_back(x);
}

dfs(0);
dfs2(0);
for (auto it : ans) cout << it << " ";
cout << endl;

return 0;
}