Sadly this is not a game, but you reminded me of Jellyfish Can't Swim in the Night.

so it's star rail

Ok I know its Arknights.

Translation: Hi (maybe Russian), Codeforces! I'm Serval (Japanese) and I speak Servalish (Chinese). Good Luck & Have Fun! (English, obviously)

They probably don't have money. From Last round didn't come money

Are you his alt account ? 😂

As an author, Saule_ is handsome too.

I think its hp's fault, they should equip a better camera on laptop lol

kinda sus!

It was supposed to be codeton I think that’s why

Fire in the hole

Bruh I'm his classmate

Actually he's in NOI2024 Sichuan Provincial Team. He just has no time to take part in CF rounds cuz he usually lives in school

same bro

me too

As a fan of Dominater069 I would like to say this.

This round is clashing with Al Ahly vs ES Tunis match — CAF Champions League Final

Ohh boy and here I was thinking why many of the solutions for task C looked very familiar with each other. Even some experts have cheated from the GFG code. Hope that they will be severely punished when the system testings are being done to find copied codes. I would like to draw the attention of the moderators to make sure that the solution codes for problem C are checked against this particular code to prevent any mass cheating

so you tried to cheat?

Suppose $$$v[0] = \lbrace 0 \rbrace$$$, so that it is of length $$$2^n$$$.

Solve recursively, on a given $$$v$$$ of length $$$2^m$$$:

• If $$$m = 0$$$, then it is solveable only if $$$0 \in v[0]$$$.

• If $$$m - 1 \in S$$$, then you can reduce to a new vector $$$u$$$ such that $$$u[i] = v[i] \cap (v[i + 2^{m-1}] - 1)$$$.

• Else, reduce to $$$u[i] = v[i] \cap v[i + 2^{m-1}]$$$.

Then solve recursively for both $$$u$$$'s (both of length $$$2^{m-1}$$$), while carrying your decision. While this may seem naive, the time complexity is $$$O(n2^n)$$$.

u can try merging the constraints as u fix one bit at a time, eg if you fix the 0th bit to be on, then u can combine all x with x+1 (since both of them share all other bits so the other bits must satisfy both their constraints), thus at each level, the array shrinks by 2, while the number of calls double by 2, so in the end the complexity is n2^n

How to solve E without TLE you mean?

My logic: You only need two things no of connected components if we only consider the black nodes in the tree .We only need to check further if the components is 1.

Now to know if the conn comp is a chain you only need to see if the distance between the 2 farthest nodes in the conn comp is equal to the number of black nodes in the tree, in a chain these two farthest nodes are leafs i.e. nodes connected to only 1 black node.

To maintain both conn comp and leafs, you only need the number of black neighbours of a node. Now i did this using segment tree on bfs ordering, since changing the colour of a node only affects its children and parent. My sol is $O(q log^2(n)) but there might be a better way.

Passed it after i changed my compiler ffs

A little bit of DP, but the main idea is adhoc anyway

No, you use DFS to calculate the distance from node A to node B — they should walk towards each other, and will first meet each other at some node C. After that they "travel together", and the number of steps is equal to the number of edges times two, minus the (distance from meeting point C to some furthest node D). Because it's best to "end" the trip in that node from which you don't have to return — so you make this ending node D the farthest one.

How to solve it ?

what was it?? I am still unable to find error in my code.262564497

Same, which got me TLE on pretest 13

after rooting the tree end points of the chain are the black nodes which dont have any black childs so you have keep track of all black nodes which have no black child

Connectivity can actually be checked in a much simpler way: The black nodes are connected iff there is exactly one black node that doesn't have a black parent.

you only have to care about black nodes which have no black child

Would be difficult to maintain. A single query can change up to N values (all neighbors).

I had the same idea during contest and managed to get $$$O(n\sqrt{n}log(n))$$$, complexity but it was to slow. You can maintain big/small vertices and recalculate "black-degree" for every vertex every $$$\sqrt{q}$$$ operations

I ended up with WA7 so I may be wrong, but I believe most of it is correct (and I probably have a bug):

• If none of the strings contain asterisks, then it is easy.

• If both contain asterisks, then check both prefixes and suffixes for equality, until you reach asterisks. If prefixes and suffixes were equal, then it should be "Yes".

Assume now that $$$s$$$ has no asterisks, and $$$t$$$ has at least one. Remove equal prefixes and suffixes, so that $$$t$$$ begins and ends with asterisk. If all of $$$t$$$ is asterisks, answer is "Yes".

Now, you need to take every substring of $$$t$$$ between a pair of asterisks, and match it to the first substring of $$$s$$$ that matches it, greedily.

It's a classical algorithm to determine whether a string can be anothers' substring, when both may contain '-' symbols, using fft in $$$O(n \log n)$$$ where $$$n$$$ is the larger of those lengths.

Now, to find the first position in which a substring of $$$t$$$, of length $$$m$$$, matches in $$$s$$$, starting from a given index $$$i$$$, you can do an exponential search:

Check if the substring appears in the substring of $$$s$$$, starting at $$$i$$$ of length $$$m$$$. If it isn't found, increase to length $$$2m$$$, and so on until it is found.

The total complexity should be $$$O(n \log^2 n)$$$.

I have the opposite opinion. In fact I found that D, F >> E.

which one ? and case ?

Can anyone please check if my solution for problem E is correct? I can't wait the system to finish and submit it.

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("-Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-funroll-all-loops,-fpeel-loops,-funswitch-loops")

#define endl '\n'

#define ull unsigned long long
#define ll long long
#define ld long double
#define int ll

#define EPS .0000001
#define MOD 1e9+7
#define PI 3.14159265358979323846

#define all(x) begin(x), end(x)
#define sor(x) sort(all(x)) 
#define rsor(x) sort(all(x), greater<>())

#define uset unordered_set
#define mset multiset
#define umset unordered_multiset

template <typename T>
using pdqu = priority_queue<T, vector<T>, greater<T>>;

void calculate();

signed main() {
    int t = 1;
    cin >> t;
    for(int i = 1; i <= t; i++) {
        calculate();
    }
}

bool color[200005];

struct DSU {
  int N;
  vector<int> size, dsu;

  DSU(int n) {
    N = n+1;
    size = vector<int> (N, 1);
    dsu = vector<int> (N);
    for(int i = 0; i < N; i++) {
      dsu[i] = i;
    }
  }

  int root(int a) {
    while(a != dsu[a]) {
      dsu[a] = dsu[dsu[a]];
      a = dsu[a];
    }
    return a;
  }

  void unite(int a, int b) {
    a = root(a);
    b = root(b);
    if(a == b) return;
    if(size[a] > size[b]) swap(a, b);
    dsu[a] = dsu[b];
    size[b] += size[a];
  }

  int get_size(int a) {
    return size[root(a)];
  }

  bool same_set(int a, int b) {
    return (root(a) == root(b));
  }

};

void calculate() {
    int n, q;
    cin >> n >> q;
    DSU dsu = DSU(n+1);
    for(int i = 1; i <= n; i++) {
        cin >> color[i];
    }
    vector<int> adj[n+1];
    vector<int> childs(n+1);
    set<int> probs;
    int u, v;
    for(int i = 0; i < n-1; i++) {
        cin >> u >> v;
        if(color[u] && color[v]) {
            dsu.unite(u, v);
            childs[u]++;
            childs[v]++;
        }
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    set<int> st;
    for(int i = 1; i <= n; i++) {
        if(color[i]) {
            st.insert(dsu.root(i));
        }
        if(childs[i] > 2) {
            probs.insert(i);
        }
    }
    int cnt = st.size();
    while(q--) {
        cin >> u;
        int rel = 0; 
        for(auto & v : adj[u]) {
            if(color[v]) rel++, childs[v]++;
            if(childs[v] > 2) {
                probs.insert(v);
            }
        }
        childs[u] = rel;
        if(color[u]) {
            cnt += rel-1;
            probs.erase(v);
        } else {
            if(rel > 2) {
                probs.insert(u);
            } 
            cnt -= (rel-1);
        }
        if(probs.size() == 0 && cnt == 1) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
        color[u] ^= 1;
    }
}

Observation 1: The blue color chess piece needs to visit all the nodes once, after it reaches a node colored red. It needs exactly this, no more or less.

Observation 2: The red and blue color piece meet most quickly if they move towards each other.

Solution: Find the midpoint where they meet using DFS/BFS. From this point as the starting point, find the minimum cost to visit all nodes at least once, again using DFS/BFS.

Here's what I did (passed all pretests):

• Calculate the midpoint node between $$$a$$$ and $$$b$$$. Let this node be $$$m$$$. (In case the distance between $$$a$$$ and $$$b$$$ is odd, take the point further away from $$$b$$$).

• If the distance between $$$a$$$ and $$$b$$$ is $$$d$$$, moving $$$B$$$ to $$$m$$$ takes $$$\lceil \frac{d}{2} \rceil$$$ steps.

• Answer will be the above steps + minimum number of steps to reach every node from $$$m$$$.

This worked but I'm not able to prove why it did. Just went with intuition.

This seems correct: (n-1)*2 — maxPath + minimumstepsNeededToMeet

Why do you have an extra case? In case distance between nodes is 1, you still need to use the same formula. (minimumstepsNeededToMeet = 1 in this case, and you will have to still subtract maxPath)

I guess because increasing the subarray length won't increase the median, we are not limited in minimum steps count so if we find maximum medians of subarray of length 3 we can eventually make the whole array consist of that median values only. suppose [3, 2, 2] subarray from some longer array. no matter if the first element is greater or less then other two equal elements, the median will be still "passed" to that third value too, that proves the fact that eventually the whole array can be filled with median values that we found in subarray length of 3.

consider some segment containing a[i]. for a[i] to be median, there should be at least one element in this segment >= a[i]. lets prove that one is enough. consider, there are at least two of them. if they are on the same side from a[i], than if distance between them >= 1, the second one doesn't change anything. otherwise, use those two consequent elements as a new segment, with a bigger median. if those two elements are on different sides, just use on of the sides, it also won't change anything. So, you just have to check that there is an element >= a[i] in 2-proximity

Go to middle point if odd then get at one edges distance.Then find the deepest node so that you do not have to return from the deepest nodes.Thn count -maximum+(n-1)*2.

Because wen d is odd then they will be separated by one edge .Think like this that red goes over all edges and at any times blue is one step behind as red finsihes blue will be one step behind.So one step more to complete.That is steps to be one edges away+ one step to cover the delay for the red

Wow interesting

I don't know why people are downvoting this comment but this comment is actually true , the reason why maspy appears before the other guy in terms of judging time because when sorting based on judging time second parameter is ignored and sorted based on minute first then based on handle name , as both of them have same value in minute parameter then they were sorted based on handle names and it looks like any handle name starting with digit comes later after handle names starting with letters

You are not allowed to use ChatGPT here either.