Fast Editorial♥

Can anyone tell me what's wrong with my solution for problem D? 267065372. It's a simple brute force solution but I still got WA on test case 2.

for problem A you can brute force it

E was awesome!!

why does my submission give TLE on test 3 , for problem B

https://mirror.codeforces.com/contest/1986/submission/267087342

I wondering for G, the constraint on n of hard version differ from the the easy very with only 5 as muplicatif factor. As in the editorial the complexity of hard is nlogn what's the expected complexity of the easy version?

Had fun! Thanks.

super fast editorial

The problem setter is very clever i mean look at the constraints(n=20) of problem D which forces you to think a some bruteforce or some DP approach so no one will go to the logical part of that which is easy at all.

Detailed Video Editorial English

C : https://youtu.be/w7yaIcNz_1w

D : https://youtu.be/UZ-zb7NZrRU

E : https://youtu.be/dCtiB_TRfms

https://mirror.codeforces.com/contest/1986/submission/267100334 [My submission]

I am getting WA on 2nd test case ? Why

Edit -> Solved by another algo

Good round! I enjoyed it.

Why the sooooooo tight memory limit in problem G? I didn't see any reason to reject solutions on the memory constant factor!! Or do you really have a meaningful $$$O(n)$$$ memory solution? Anyway, if an acceptable solution uses $$$1\cdot n\log n$$$ memory, why to reject $$$2\cdot n\log n$$$?

No sample code?

Can anyone please tell me why my solution 267122161 for Problem D is giving Wrong Answer on test case 2?

can someone explain how to solve problem B? I was really stuck in problem B, especially thinking if the a[i][j] is a corner piece, edge piece, or neither. Thanks, really appreciate it!

For problem F, I used a unique method yesterday to find the bridge edges in this graph (which seems to be an undirected graph). While some parts may be a bit technical, I want to record and share it with everyone.

First, I used a union-find data structure to find a valid spanning tree (assuming that edge weights are directly assigned to the child nodes). Then, for the remaining edges $$$(u_i, v_i)$$$ that are not in the tree, I increment the path $$$(u_i, v_i)$$$ by one, because this forms a cycle, and cycles do not have bridge edges. This can be achieved through the LCA (Lowest Common Ancestor) and tree difference methods.(maybe this name, sorry for my poor English.)

Here is the submission. 267081057

However, after careful consideration, I realized that we can use a hashing and xor approach. Each time we cover a path, we assign a random value in the range $$$[0, 2^{64})$$$. Due to the properties of xor, the values will cancel out above the LCA, which is equivalent to checking if the path has been covered. Finally, we just need to calculate the subtree sizes in the tree and update the answer accordingly. This method eliminates the need to find the LCA.

Here is the submission. 267125590

Very interesting problemset .

my lazy brain could only thought of the dp solution for the problem E. Am I too dumb to realise the claver and O(N) soln of author ??

Man, I overthinked a lot on D and at last ended up doing it with DP, i got tle because i was using n^4 * t, but just with a simple change (removing prev index and using a bool at its place, as partition can be either of size 2 or 1 I was able to Pass it)

ll rec(int i, int prev, int left, int canskip, string &s, vector<vector<vector<vector<ll>>>> &dp)
{
    ll n = s.length();
    if (left == 0)
    {
        ll val = stoll(s.substr(i, n - i));

        return val;
    }

    if (dp[i][prev][left][canskip] != -1)
    {
        return dp[i][prev][left][canskip];
    }

    if (i >= s.length())
    {
        return 1e9;
    }
    ll add = 1e18, mul = 1e18;

    if (prev)
    {
        add = stoll(s.substr(i-1, 2)) + rec(i + 1, 0, left - 1, canskip, s, dp);
        mul = stoll(s.substr(i-1,2)) * rec(i + 1, 0, left - 1, canskip, s, dp);
    }
    else
    {
        add = stoll(s.substr(i,1)) + rec(i + 1, prev, left - 1, canskip, s, dp);
        mul = stoll(s.substr(i,1)) * rec(i + 1, prev, left - 1, canskip, s, dp);
    }
    ll dont = 1e9;
    if (canskip)
    {
        dont = rec(i + 1, 1, left, 0, s, dp);
    }

    return dp[i][prev][left][canskip] = min(add, min(mul, dont));
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    gin(t);
    while (t--)
    {
        gin(n);
        string s;
        cin >> s;
        vector<vector<vector<vector<ll>>>> dp(n + 1, vector<vector<vector<ll>>>(3, vector<vector<ll>>(n + 1, vector<ll>(3, -1))));
        cout << rec(0, 0, n - 2, 1, s, dp) << endl;
        // Always check if the input is 2n
    }
    // cout<<fixed<<setprecision(10);
    // cerr<<1000*((double)clock())/(double)CLOCKS_PER_SEC;
}

Either codeforces has a bigger stack or I suspect weak tests for problem F. My recursive DFS got AC and locally I am able to segfault it with giving it a path on 10^5 vertices.

.

the Editorial Is not listed within the contest

problem c has a similar idea to this

Can someone explain problem G

C has been hacked? How?

Fast Editorial!

What is actually the "count array" in G2?

In problem E, why is it advantageous to consider only the odd indices for removal if $$$m$$$ is odd?

Edit: I get it now. Choosing even indices makes the answer worse because you are now pairing up non-adjacent elements, which makes the answer larger.

Why my problem B solution is still in queue☠️, Although I remember that it was accepted last night

in problem E I'm sorting the array and matching each element with the closest one but this greedy is giving wrong at test 10 my answer is 15 but the correct is 14 is this approach really wrong ???

If anyone searching for dp solution for problem D. Here is my solution that got accepted:

ll dp[21][21][101];
ll helper(ll i, ll cnt, string s,string a1){
    ll n=s.size();
    if(a1.size()>2){
        return 1e9;
    }
    else{
         if(cnt>n-2 || i>n){
        return 1e9;
    }
        ll y=stoi(a1);
        //debug(a1);
        if(cnt==n-2 && i==n){
        return stoi(a1);
    }
    if(dp[i][cnt][y]!=-1){
        return dp[i][cnt][y];
    }
    ll a=INF,b=INF,c=INF;
    string x="";
    if(cnt<n-2 )a=stoi(a1)+helper(i+1,cnt+1,s,x+s[i]);
    if(cnt<n-2 )b=stoi(a1)*helper(i+1,cnt+1,s,x+s[i]);
    c=helper(i+1,cnt,s,a1+s[i]);
    return dp[i][cnt][y]=min({a,b,c});
    }
}
void solve()
{
    ll n;
    cin>>n;
    string s;
    cin>>s;
    string a="";
    a+=s[0];
    memset(dp,-1,sizeof(dp));
    //<vector<vector<ll>>>v(n+1,vector<vector<ll>>(n,vector<ll>()))
    //debug(help("2+3+3+11"));
    //map1[a]=1;
    ll ans=helper(1,0,s,a);
    //debug(map1);
    print(ans);
}

I think in Problem-D solution the case where a "0"(zero) exists the answer must be zero, is missing a case where n==3 because you will see p0q, which will not lead to zero, it will lead to min(p*10+q,p+q,p*10*q). Else everything is fine

For Problem D : Simple DP solution in O(N)

Why did i get a run time error for C? 267036690

The cheating is going out of hand,I refuse to believe that more than 6k did D.

Man dropped editorial as soon as the contest ends. Nice work.

F was amazing! Please add more graph problems in Div3

Can the F one be done using DSU?

why did i get runtime error for problem d? Please help me out 267184148

74TrAkToR There is a mistake in the Problem-D editorial.

You mentioned If there is at least one 0 , the answer is 0 . We can simply place all signs as ×.

This is not true even for a given test casen=3 and s='901' whose answer will be a 9 and not a zero.

I think in D if all numbers are 1 then answer should be 11 not 1 because we will need to concatenate two numbers.

why such tight memory constraints on G? why cannt they give more memory???? I got G1 accepted, and G2 was MLE on 43rd testcase... sad life...

Problem 1986D - Mathematical Problem solution:

Key observation: As we can use only n-2 sign (+, x), so there must be at least one two-digit number. Then just find the minimum answer as asked.

-Time Complexity O(n ^ 2)

        int n; 
	string s;
	cin >> n >> s;
	int ans = INT_MAX;
	for(int i = 1; i<n; i++){
		int num = stoi(s.substr(i-1, 2)); 
		for(int j = 0; j<n; j++){
			if(j==i-1 || j==i) continue;
			int cur = s[j]-'0';
			num = min(num*cur, num + cur);
		}
		ans = min(ans, num);
	}
	cout << ans << '\n';

can tell me anyone what is wrong in my code 267195219 // i have basically find every 2 digit pair and min number towards left and towrards right and then left — central — right 4 cases * * + * * + + + it is frustrating

Why this contest is showing in unrated?

Can anyone tell me what's wrong with my solution for problem D? 267205625 It's a simple brute force solution but I still got WA on test case 2.

Clean and fast Editorial

Can someone explain for F. How to Find if a edge is a bridge or not.

Can anyone please review my Dp soln and tell what is wrong here, either any logical error or overflow. The output seems like it is an overflow, if it is then how should i avoid it?

#include <bits/stdc++.h>
using ll = long long;
using namespace std;
const ll MOD = 1e9 + 7;

ll f(int i, bool taken, string& s, vector<vector<ll>>& dp){
    int n = s.length();
    //Base cases
    if (i <= 0) return (s[0] - '0');

    if(dp[i][taken] != -1) return dp[i][taken];

    //Doing stuffs on index
    ll val = (s[i] - '0');
    ll pair = LLONG_MAX;
    if(!taken && i > 0 && i < n - 1) pair = stoll(s.substr(i - 1, 2));

    if(taken){
        return dp[i][taken] = min(val + f(i - 1, false, s, dp), val * f(i - 1, false, s, dp)); //If pair of digit already taken, go digit by digit
    }
    else return dp[i][taken] = min({val + f(i - 1, false, s, dp), val * f(i - 1, false, s, dp), //else we have one more option to take a pair
                                    pair + f(i - 2, true, s, dp), pair * f(i - 2, true, s, dp)});
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;
        string s;
        cin >> s;

        if(n == 2){
            cout << stoll(s) << endl;
            continue;
        }

        vector<vector<ll>> dp(n, vector<ll> (2, -1));

        cout << f(n - 1, false, s, dp) << endl;
    }

    return 0;

Update-1: The Base case was wrong and in if(taken){} there should be "true" in further recursive calls. Base case:

 if(i == 1 && taken == false){
        return stoll(s.substr(i - 1, 2));
    }
    if(i == 0) return (s[0] - '0');

This helped in avoiding overflow and correct output on many test cases but for few test case the answer was wrong.

Update-2: Final Accepted code :)

#include <bits/stdc++.h>
using ll = long long;
using namespace std;
const ll MOD = 1e9 + 7;

ll f(int i, bool taken, string& s, vector<vector<ll>>& dp){
    int n = s.length();
    //Base cases
    if(i == 1 && taken == false){
        return stoll(s.substr(i - 1, 2));
    }
    if(i == 0) return (s[0] - '0');

    if(dp[i][taken] != -1) return dp[i][taken];

    //Doing stuffs on index
    ll val = (s[i] - '0');
    ll pair = INT_MAX;
    if(!taken && i > 0 && i < n) pair = stoll(s.substr(i - 1, 2));


    if(taken){
        return dp[i][taken] = min(val + f(i - 1, true, s, dp), val * f(i - 1, true, s, dp)); //If pair of digit already taken, go digit by digit
    }
    else return dp[i][taken] = min({val + f(i - 1, false, s, dp), val * f(i - 1, false, s, dp), //else we have one more option to take a pair
                                    pair + f(i - 2, true, s, dp), pair * f(i - 2, true, s, dp)});
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;
        string s;
        cin >> s;

        if(n == 2){
            cout << stoll(s) << endl;
            continue;
        }

        vector<vector<ll>> dp(n, vector<ll> (2, -1));

        cout << f(n - 1, false, s, dp) << endl;
    }

    return 0;
}

Can anyone tell me whats wrong with my prefix and suffix handling in problem in case of odd length 267095361

Can someone explain me F better? I can find the bridges, but can't go any further. Run a single dfs in each bridge will get TLE. I didnt get the size of subtree part.

In problem E any one can help on how to approach the idea of excluding one element using DP

Changing map to a sorted vector of elements + binary search works in G2, the time complexity is the same but i can't figure out why it removes the MLE i get with map, since intuitively, i am storing count in map and elements in vector, the storage in map is more sparse, is this happening because in testcase 43 the array values are such that, it leads to lower count values in map and thus, reducing the advantage of sparseness?

Map submission

Vector submission

why show node for us? still have questions

Can anyone pls provide cpp code for E problem , doing the same thing but got tle

/* https://mirror.codeforces.com/contest/1986/submission/267290277

can anyone help me ?I am getting TLE in test case 27. Thanks in advance/* ~~~~~

include <bits/stdc++.h>

using namespace std;

define pi (3.141592653589)

define mod 1000000007

define ll long long int

define all(c) c.begin(), c.end()

define min3(a, b, c) min(c, min(a, b))

define rfl(i, a, n) for (int i = n — 1; i >= a; i--)

define fl(i, a, n) for (ll i = a; i < n; i++)

define ct(x) cout << x << endl

define rd(a, n) fl(i, 0, n) cin >> a[i]

define wrt(a, n) fl(i, 0, n) cout << a[i] <<

define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

// char Array to int Using atoi() like string s // C++ string to int Using stoi() like char str[50]

int main() { fast int t = 1; cin >> t; while (t--) {

ll i,
    j, k, n;
cin >> n >> k;
ll arr[n+5];
rd(arr, n);
unordered_map<ll, vector<ll>> mp;
sort(arr, arr + n);

fl(i, 0, n) mp[arr[i] % k].push_back(arr[i]);

ll ans = 0;
ll odd = n % 2;

ll oc = 0;
for (auto it : mp)
    if (it.second.size() % 2)
        oc++;

if (n % 2 < oc)
{
    cout << -1 << endl;

continue; } for (auto &it : mp) { int sz = it.second.size(); if (sz % 2 == 1) {

ll s = 0;

            vector<ll> pref(it.second.size() + 5, 0);
            for (int i = 0; i < it.second.size(); i++)
            {
                if (i % 2)
                    s += (it.second[i] - it.second[i - 1]) / k;
                pref[i] = s;
            }
            // cout<<endl;

            s = 0;
            ll temp = 1e18;
            for (int i = sz - 1; i >= 0; i--)
            {
                if ((i % 2))
                {
                    s += (it.second[i + 1] - it.second[i]) / k;

                    // pref[i]=s;
                }
                else
                {

                    temp = min(temp, pref[i] + s);
                }
            }

            ans += temp;
        }


    else
    {

        for (int i = 1; i < sz; i += 2)
        {
            ans += abs(it.second[i] - it.second[i - 1]) / k;
        }
    }
}

cout << ans << endl;
}
return 0;

} ~~~~~

can anyone tell the problem with my code on D 267075434 it was wrong on test case 4 https://mirror.codeforces.com/contest/1986/submission/267075434

my submission for B. works on my computer but not here :267313352 Help.

Would like to add some of my thoughts on G to the discussion, this might be a more intuitive approach.

The first step is still to simplify $$$\frac{p_i}{i}$$$ to $$$\frac{a_i}{b_i}$$$. Now we can write out the following brute force pseudocode:

$$$\texttt{for } a_i:$$$

$$$\quad\texttt{for } b_j | a_i:$$$

$$$\quad\quad\texttt{for } a_j:$$$

$$$\quad\quad\quad\texttt{for } b_i | a_j:$$$

$$$\quad\quad\quad\quad\texttt{res += } f(a_i,b_i)f(a_j,b_j)$$$

Where $$$f(a,b)$$$ counts the number of datapoints with simplist form $$$\frac{a}{b}$$$. This is sparse with at most n entries, so we can use something like $$$\texttt{std::vector<std::map<int, int> >}$$$ to represent it.

Now we can reduce the number of loops by precalculating a "factor prefix sum" on the table $$$f$$$. The idea is very similar to prefix sum. Let's denote $$$g(a,b) = \Sigma_{b'|b}f(a,b')$$$. Then

$$$\texttt{for } a_i:$$$

$$$\quad\texttt{for } a_j:$$$

$$$\quad\quad\texttt{res += } g(a_i,a_j)g(a_j,a_i)$$$

An elegant form! Unfortunately it doesn't work. Aside from the double loop, we now have a dense table $$$g$$$ (just consider the edge case that $$$f(a,1) = 1$$$ for any $$$a$$$, then $$$g$$$ would have positive value for every $$$(a,b)$$$ pair). So even building the table would take $$$O(n^2)$$$ space and time.

The trick is to change the subscript that we perform the sum operation. Let's first rearrange our original brute force algorithm:

$$$\texttt{for } b_j:$$$

$$$\quad\texttt{for } b_j | a_i:$$$

$$$\quad\quad\texttt{for } b_i:$$$

$$$\quad\quad\quad\texttt{for } b_i | a_j:$$$

$$$\quad\quad\quad\quad\texttt{res += } f(a_i,b_i)f(a_j,b_j)$$$

So we first loop over each $$$b_j$$$, then all multiples of $$$b_j$$$, then each $$$b_i$$$, then all multiples of $$$b_i$$$.

Similar to $$$g$$$, define the prefix sum table $$$h(a,b) = \Sigma_{a|a'}f(a',b)$$$. Then we have

$$$\texttt{for } b_j:$$$

$$$\quad \texttt{for } b_i:$$$

$$$\quad\quad \texttt{res += } h(b_j,b_i)h(b_i,b_j)$$$

The difference between $$$h$$$ and $$$g$$$ is that $$$h$$$ is sparse: we can see that each $$$(a,b)$$$ adds its $$$f$$$ value to exactly $$$\sigma_0(a)$$$ points (the number of divisors of $$$a$$$), so in total the space complexity is $$$O(nlogn)$$$.

Finally because the table is sparse, we can optimize the double loop as well, by just looping over the keys with positive value:

$$$\texttt{for } b_j:$$$

$$$\quad \texttt{for } b_i \texttt{ in } [b_i | h(b_j,b_i) > 0]:$$$

$$$\quad\quad \texttt{res += } h(b_j,b_i)h(b_i,b_j)$$$

If we are use map here, the time complexity would be $$$O(nlog^2n)$$$. This solution should be good enough to pass G1. implementation

However, the $$$O(nlogn)$$$ time is not good enough to pass G2 (or maybe it is, just that map has a big constant, but let's just push for the best solution). How do we optimize this? A natural thing to do for those 2D tables is to optimize away one of the dimensions, usually the row dimension. However, currently our algorithm uses values from both $$$b_i$$$ and $$$b_j$$$ row, so for one of the rows, we need to sacrifice some extra time to calculate the prefix sum from the raw $$$f$$$ table directly. Since we are looping in $$$b_j$$$ first, let's replace $$$h(b_i,b_j)$$$ with its definition (based on $$$f$$$):

$$$\texttt{for } b_j:$$$

$$$\quad \texttt{for } b_i:$$$

$$$\quad\quad \texttt{for } b_i | a_j:$$$

$$$\quad\quad\quad \texttt{res += } h(b_j,b_i)f(a_j,b_j)$$$

Now $$$h(b_i,b_j)$$$ only uses information from the current row, $$$b_j$$$. To illustrate this, let's change its notation to $$$h_{b_i}(b_j)$$$ (this is in fact the "count array" the official editorial is referring to), so it becomes a 1D table.

Change the order of loop:

$$$\texttt{for } b_i:$$$

$$$\quad \texttt{for } b_i | a_j:$$$

$$$\quad\quad \texttt{for } b_j:$$$

$$$\quad\quad\quad \texttt{res += } h_{b_i}(b_j)f(a_j,b_j)$$$

This order change allows us to utilize the sparsity of table $$$f$$$:

$$$\texttt{for } b_i:$$$

$$$\quad \texttt{for } b_i | a_j:$$$

$$$\quad\quad \texttt{for } b_j \texttt{ in } [b_j|f(a_j,b_j)=1]:$$$

$$$\quad\quad\quad \texttt{res += } h_{b_i}(b_j)$$$

This algorithm should pass G2. implementation The time complexity is $$$O(200n + nlogn)$$$, where $$$200$$$ is the max number of divisors for numbers <= 5e5. Space complexity is $$$O(n)$$$.

Note that in the implementation you also need to take care of some duplicate cases.

Hopefully this helps those who are strugglign with this problem.

https://mirror.codeforces.com/contest/1986/submission/267420939

G2 Question can anyone help me, how to get rid of TLE.

Sorry for asking. Why doesn't my code work on problem E? Here's the submission.

hey how i can increase my speed in contest a guy solves the same number of problems as me but got much better rank than me

Has Anyone done the DP solution for the D problem?

I think it can be solved using the Partition DP pattern(Similar to the MCM problem), but I couldn't able to code it.

Thanks in advance.

my solution for 1986B-15 is shown to give wrong answer on test case 3 i cant find the reason

https://mirror.codeforces.com/problemset/submission/1986/268558565

Can anyone tell me what is wrong with this solution for the problem F? I find the bridge and calculate the maximum pairs of vertices not reachable, then the answer is $$$ n * (n + 1) / 2 - pairs_cut $$$. But I think I messed up because some answers are negative.

ll n, m;
vvi adj;
vi visited, tin, low;
vll sz;
int times;
ll edgesCut;

void dfs1(int u, int p) {
    visited[u] = 1;
    sz[u] = 1;
    tin[u] = low[u] = times;
    times++;

    for(int to : adj[u]) {
        if(to == p) continue;
        if(!visited[to]) {
            dfs1(to, u);
            low[u] = min(low[u], low[to]);
            sz[u] += sz[to];

            // BRIDGE
            if(tin[u] < low[to]) {
                edgesCut = max(edgesCut, sz[to] * (n - sz[to]));
            }
        } else {
            low[u] = min(low[u], low[to]);
        }
    }
}

void solve(){
    cin >> n >> m;
    times = 0;
    edgesCut = 0;
    adj = vvi(n);
    visited = vi(n);
    tin = vi(n);
    low = vi(n);
    sz = vll(n);

    rep(i, m) {
        int a, b; cin >> a >> b;
        a--, b--;
        adj[a].pb(b);
        adj[b].pb(a);
    }

    dfs1(0, 0);

    int ans = n * (n - 1) / 2 - edgesCut;
    cout << ans << "\n";
}

.

Why is it more advantageous to remove the odd-indexed elements in problem E?

Can anyone help me improve my code for G1? I got TLE and still dont know how to solve bc seems like my solution is opposite with author's code :)

/*
o((>ω< ))o
o(≧口≦)o
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
#define int ll
#define F first
#define S second
#define yes cout << "YES" << endl
#define no cout << "NO" << endl

int n,cnt,tmp;
vector<int> p(1e5+10),a(1e5+10),b(1e5+10);
vector<vector<int>> vt(1e5+1, vector<int>());

void solve(){
    cin >> n; for (int i = 1; i <= n; i++) cin >> p[i];
    if (n == 1){
        cout << 0 << endl;
        return;
    }
    for (int i = 1; i <= n; i++){
        tmp = __gcd(i,p[i]);
        a[i] = p[i]/tmp;
        b[i] = i/tmp;
        vt[b[i]].push_back(i);

    }

    cnt = 0;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j*j <= a[i]; j++){
            if ((a[i] % j) == 0){
                if (vt[j].size() != 0 && i < vt[j][vt[j].size()-1]){

                    tmp = upper_bound(vt[j].begin(),vt[j].end(),i)-vt[j].begin();

                    for (int k = tmp; k <= vt[j].size()-1; k++) { // I think the reason is here but how to improve it :)
                        cnt += ((a[vt[j][k]] % b[i]) == 0);
                    }

                }


                if (j != (a[i]/j)){

                    if (vt[a[i]/j].size() != 0 && i < vt[a[i]/j][vt[a[i]/j].size()-1]){

                        tmp = upper_bound(vt[a[i]/j].begin(),vt[a[i]/j].end(),i)-vt[a[i]/j].begin();
                        for (int k = tmp; k <= vt[a[i]/j].size()-1; k++) cnt += ((a[vt[a[i]/j][k]] % b[i]) == 0); // The same as above :)

                    }

                }
            }
        }
    }
    cout << cnt << endl;

    for (int i = 1; i <= n; i++) vt[i].clear();
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t; cin >> t; while (t--)
    solve();
}

Ahh also my last submission here: https://mirror.codeforces.com/contest/1986/submission/272568165

Thanks a lot guys :)

Why does using unordered_map TLE at E