Comments - Codeforces

→ Pay attention

Before contest
Codeforces Round 1099 (Div. 2)
41:27:49
Register now »

*has extra registration

→ Top rated

#	User	Rating
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3611
4	jiangly	3583
5	strapple	3515
6	tourist	3470
7	Radewoosh	3415
8	Um_nik	3376
9	maroonrk	3361
10	XVIII	3345

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	Qingyu	162
2	adamant	148
3	Um_nik	146
4	Dominater069	143
5	errorgorn	141
6	cry	138
7	Proof_by_QED	136
8	YuukiS	135
9	chromate00	134
10	soullless	133

View all →

→ Find user

→ Recent actions

Detailed →

Comments

XiaoXia

On Sugar_fan → Hacking Incorrect XOR Hashing with mt19937_64, 3 weeks ago

It is easy to avoid being hacked, just make some non-bitwise operation on rng() randomly.

Like this:

std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
for (int i = 0; i < n; i++) {
    a[i] = rng() / 3;
}

Do not just divide or multiply it by $$$2^k$$$ or it will just degenerate into taking a subset of rng(). (which is still hackable)

XiaoXia

On __baozii__ → Codeforces Round 1087 (Div. 2) Editorial, 2 months ago

It seems like that it is not O(nq) but O(n^2q) when the string constructed wisely.(tho I don't know if such a string existed.)

XiaoXia

On AksLolCoding → Codeforces Round 1084 (Div. 3) Editorial, 2 months ago

revised

XiaoXia

On AksLolCoding → Codeforces Round 1084 (Div. 3) Editorial, 3 months ago

Maybe you need 3 mod NTT: convolution_mod_1000000007 (Which calculate the ans with three different MOD and merge them with CRT(Chinese Remainder Theory) to get ans in MOD=1e9+7)

XiaoXia

On StarSilk → FST on test 1, 5 months ago

You should test it with codeforces's "Custom Invocation", which will be more consistent with the actual situation of the online judge.

XiaoXia

On wjy666 → Codeforces Round 1048 (Div. 1, Div. 2), 8 months ago

Just try to make $$$x = 21, y = 2^{5 + 1} - 21 = 43$$$ to $$$x = y = 2^k = 32$$$:

$$$(x, y) = (21, 43) \longleftarrow^1 (42, 22) \longleftarrow^2(20, 44) \longleftarrow^1 (40, 24)\longleftarrow^2(16, 48)\longleftarrow^1(32, 32)$$$

Then you can get the answer by reverse the sequence "12121" -> "12121"

XiaoXia

On henotrix → Codeforces Round 1045 (Div. 2) Editorial, 9 months ago

For D, we can construct the whole operation sequences in $$$\mathcal{O}(n)$$$.

Code

auto Paint = [&](int r, int k) -> std::pair<std::vector<int>, std::vector<int>> {
    std::vector<int> mark(n + 1);
    std::vector<int> list;
    auto dfs = [&](auto&& self, int now, int from) -> void {
        for (auto nxt : edg[now]) {
            if (nxt == from) continue;
            self(self, nxt, now);
            mark[now] |= mark[nxt];
        }
        if (mark[now]) list.push_back(now);
    };
    mark[k] = 1;
    dfs(dfs, r, -1);

    return {mark, list};
};
auto [h, list] = Paint(a, b);// a, b is the end point of the diameter

std::vector<std::array<int, 3>> ans;
auto work = [&](int v, int f) {
    std::vector<int> vis;
    vis.push_back(f);

    auto dfs = [&](auto&& self, int now, int from) -> void {
        vis.push_back(now);
        for (auto nxt : edg[now]) {
            if (nxt == from || h[nxt]) continue;
            self(self, nxt, now);
        }
    };

    dfs(dfs, v, -1);

    for (int i = 2; i < vis.size(); i++) {
        ans.push_back({vis[i - 2], vis[i - 1], vis[i]});
    }
};

for (int i = list.size() - 1; i; i--) {
    work(list[i], list[i - 1]);
}

And implement the checker in $$$\mathcal{O}(n\log^2n)$$$

Part of checker

#include<bits/stdc++.h>
#define int i64 /* R.I.P */
#define all(x) std::begin(x), std::end(x)
#define rall(x) std::rbegin(x), std::rend(x)
using i64 = long long;
using u64 = unsigned long long;
using ld = long double;

#define LINE std::cerr << __LINE__ << "}\n";

void solve() {
    int n;
    std::cin >> n;
    std::vector edg(n + 1, std::set<int>());

    for (int i = 1; i < n; i++) {
        int x, y;
        std::cin >> x >> y;
        edg[x].insert(y);
        edg[y].insert(x);
    }

    std::vector<int> mp(n + 1), rmp(n + 1);
    std::iota(mp.begin(), mp.end(), 0);
    std::iota(rmp.begin(), rmp.end(), 0);

    auto calc_Diameter = [&]() -> std::array<int, 3> {// diameter, a, b
        auto getdis = [&](int r) {
            std::vector<int> dis(n + 1, 1e9);

            std::queue<int> q;
            q.push(r);
            dis[r] = 0;
            while (q.size()) {
                int now = q.front(); q.pop();

                for (auto nxt : edg[now]) {
                    if (dis[nxt] > dis[now] + 1) {
                        dis[nxt] = dis[now] + 1;
                        q.push(nxt);
                    }
                }
            }
            return dis;
        };
        
        auto d0 = getdis(1);
        int a = 1;
        for (int i = 1; i <= n; i++) {
            if (d0[i] > d0[a]) {
                a = i;
            }
        }

        auto d1 = getdis(a);
        int len = d1[1];

        int b = 1;
        for (int i = 1; i <= n; i++) {
            if (d1[i] > d1[b]) {
                b = i;
                len = d1[i];
            }
        }
        
        return {len, a, b};
    };

    auto [len, a, b] = calc_Diameter();

    auto show = [&]() {
        std::cout << "==========\n";
        for (int i = 1; i <= n; i++) {
            std::cout << mp[i] << " ";
        } std::cout << "\n";
        for (int i = 1; i <= n; i++) {
            std::cout << rmp[i] << " ";
        } std::cout << "\n";

        for (int i = 1; i <= n; i++) {
            for (auto j : edg[mp[i]]) {
                if (i < rmp[j]) {
                    std::cout << i << "-" << rmp[j] << "]\n";
                }
            }
        }

        std::cout << "==========\n";
    };

    auto Range_Vaild = [&](int v) -> bool {
        return v >= 1 && v <= n;
    };
    auto Edge_Vaild = [&](int a, int b) -> bool {
        return edg[mp[a]].contains(mp[b]);
    };
    auto check_vaild = [&](std::vector<std::array<int, 3>> ans) -> bool {
        for (auto [a, b, c] : ans) {
            // show();
            // std::cout << a << ", " << b << ", " << c << "]\n";
            if (!Range_Vaild(a)) {
                std::cout << "wrong answer a's range invaild";
                return 0;
            }
            if (!Range_Vaild(b)) {
                std::cout << "wrong answer b's range invaild";
                return 0;
            }
            if (!Range_Vaild(c)) {
                std::cout << "wrong answer c's range invaild";
                return 0;
            }
            if (a == b) {
                std::cout << "wrong answer a should not be equal to b";
                return 0;
            }
            if (b == c) {
                std::cout << "wrong answer b should not be equal to c";
                return 0;
            }
            if (a == c) {
                std::cout << "wrong answer a should not be equal to c";
                return 0;
            }
            if (!Edge_Vaild(a, b)) {
                std::cout << "wrong answer edge (a, b) does not exist before the current operation";
                return 0;
            }
            if (!Edge_Vaild(b, c)) {
                std::cout << "wrong answer edge (b, c) does not exist before the current operation";
                return 0;
            }

            if (edg[mp[b]].size() < edg[mp[c]].size()) {
                for (auto nxt : edg[mp[b]]) {
                    if (rmp[nxt] == a || rmp[nxt] == c) continue;
                    edg[mp[c]].insert(nxt);
                    edg[nxt].insert(mp[c]);
                    edg[nxt].erase(mp[b]);
                }
                edg[mp[b]].clear();
                edg[mp[b]].insert(mp[a]);
                edg[mp[b]].insert(mp[c]);
            } else {
                std::swap(mp[b], mp[c]);
                rmp[mp[b]] = b;
                rmp[mp[c]] = c;                

                for (auto nxt : edg[mp[b]]) {
                    edg[mp[c]].insert(nxt);
                    edg[nxt].insert(mp[c]);
                    edg[nxt].erase(mp[b]);
                }
                edg[mp[b]].clear();

                edg[mp[a]].erase(mp[c]);
                edg[mp[c]].erase(mp[a]);
                edg[mp[c]].erase(mp[c]);

                edg[mp[b]].insert(mp[a]);
                edg[mp[a]].insert(mp[b]);
                edg[mp[b]].insert(mp[c]);
                edg[mp[c]].insert(mp[b]);
            }            
        }
        // show();
        return 1;
    };

    if (n - 1 - len == 0) {
        std::cout << -1 << "\n";
    } else {
        auto Paint = [&](int r, int k) -> std::pair<std::vector<int>, std::vector<int>> {
            std::vector<int> mark(n + 1);
            std::vector<int> list;
            auto dfs = [&](auto&& self, int now, int from) -> void {
                for (auto nxt : edg[now]) {
                    if (nxt == from) continue;
                    self(self, nxt, now);
                    mark[now] |= mark[nxt];
                }
                if (mark[now]) list.push_back(now);
            };
            mark[k] = 1;
            dfs(dfs, r, -1);

            return {mark, list};
        };
        auto [h, list] = Paint(a, b);// a, b is the end point of the diameter

        std::vector<std::array<int, 3>> ans;
        auto work = [&](int v, int f) {
            std::vector<int> vis;
            vis.push_back(f);

            auto dfs = [&](auto&& self, int now, int from) -> void {
                vis.push_back(now);
                for (auto nxt : edg[now]) {
                    if (nxt == from || h[nxt]) continue;
                    self(self, nxt, now);
                }
            };

            dfs(dfs, v, -1);

            for (int i = 2; i < vis.size(); i++) {
                ans.push_back({vis[i - 2], vis[i - 1], vis[i]});
            }
        };

        for (int i = list.size() - 1; i; i--) {
            work(list[i], list[i - 1]);
        }

        assert(ans.size() == n - 1 - len);
        assert(check_vaild(ans));

        std::cout << ans[0][0] << " " << ans[0][1] << " " << ans[0][2] << "\n";
    }

    auto [len_, _, __] = calc_Diameter();
    if (len_ != n - 1) {
        std::cout << "wrong answer after all operation the tree is still not a path graph\n";
    }
}

signed main() {
    std::cin.tie(0) -> sync_with_stdio(false);
    int t = 1;
    std::cin >> t;
    while (t--) solve();
    return 0;
}

If the problem D is changed to this, how would it be rated in the cf rating?

XiaoXia

On henotrix → Codeforces Round 1045 (Div. 2), 9 months ago

+10

As a tester, the problemset is one of my most favourite one. Good luck, hope you would enjoy it.

XiaoXia

On YuukaKazami → Code Force Beta Round 19 Solution, 10 months ago

just weak system testing

XiaoXia

On Dragmon → Codeforces Round 1033 (Div. 2) and CodeNite 2025, 11 months ago

As a tester, hope all the participants can change the color of handle to the next rating level

XiaoXia

On SpyrosAliv → Codeforces Round 1020 (Div. 3) Editorial, 13 months ago

Why hasn't the implementation code uploaded yet?

XiaoXia

On atcoder_official → UNIQUE VISION Programming Contest 2025 Spring (AtCoder Beginner Contest 398) Announcement, 14 months ago

E is disturbing for such a strict output format.

XiaoXia

On MikeMirzayanov → New Year's Eve Update: Random Problems for Mashups, 17 months ago

GYM -> MUSHUP -> create a new mushup -> click the "Add random problems" under the problem list

XiaoXia

On MikeMirzayanov → New Year's Eve Update: Random Problems for Mashups, 17 months ago

This feature is only for mushup, you can access it through:

GYM -> MUSHUP -> create a new mushup -> click the "Add random problems" under the problem list

(seems unfriendly for those who are unfamiliar with MUSHUP? (Including me))

XiaoXia

On MikeMirzayanov → User Lists, 17 months ago

How can I remove a list from "Shared with me"? I wanna keep it empty.

XiaoXia

On PeruvianCartel → I reached GM, this is insane! (sequel to my previous post), 18 months ago

+10

Congrats

XiaoXia

On Misuki → Codeforces Round 967 (Div. 2), 21 month(s) ago

As a newcomer, you have 1200 hidden initial ratings, divided into the first five contests sent to you. If you don't perform well in the first 5 contests, the rating sent to you will be reduced, but you will not be given negative ratings. The following contests after first 5 contrsts will directly settle your total rating. So all in all, instead of going up to 783, you're going down from 1200 to 783.

XiaoXia

On Misuki → Codeforces Round 967 (Div. 2), 21 month(s) ago

Thanks, I see it. It seems like that it is easy to find such data.

XiaoXia

On Misuki → Codeforces Round 967 (Div. 2), 21 month(s) ago

Can anyone tell me why my code for D got accepted with time complexity of O(n²)?

Is there any data could hack my solution: 277446088?

XiaoXia

On awoo → Educational Codeforces Round 169 [Rated for Div. 2], 21 month(s) ago

How to gain rating in EDU Round? I've droped the rating at almost every the EDU round.

XiaoXia

On jdurie → Codeforces Round #941 (Div. 1, Div. 2) Editorial, 2 years ago

The color you fill the rectangle with is the color that the cells you select are.

XiaoXia

On MikeMirzayanov → Codeforces Single Account Policy: zh0ukangyang is Removed from the Rating, 2 years ago

+33

There have been so many mistakes you probably can't even count them in Goodbye 2023. Here's just a few: 1.Weak pretests in A. 2.Incorrect and self-contradicting usage of "divisor" in the statement of B. 3.Incorrect and self-contradicting usage of "parent" in the statement of E. 4.F has appeared previously. 5.G doesn't have a proven solution. 6.Author's solution of G is incorrectly implemented. 7.H is too easy. 8.H is in OEIS. --copied from other's comment.

Just turn to that blog and you will find the truth.

The only programming contests Web 2.0 platform

Server time: May/20/2026 00:07:12 (g2).

Desktop version, switch to mobile version.

Supported by