TLE in Sequence Land

I was solving Sequence Land
My code :
(Optimised one :

Both my submissions give TLE on last test case. Can anyone please help me optimise it?

You can improve your check() function.

This is your code:

bool check(int u, int v){
    int c = 0;
    for (auto x : id[u]){
        for (auto y : id[v]){
            if (x == y)
    if (c >= k)
        return true;
    return false;

This is O(n^2). It can be improved to O(n) if you use unordered_map:

for (int i = 1; i < n; ++i)
    for (int j = i+1; j <= n; ++j)
        unordered_map <int, int> m;
        int cnt = 0;
        for (int e : a[i]) ++m[e];
        for (int e : a[j])
            if (m[e] == 2) ++cnt;
        if (cnt >= k)

You have a nested for loop that takes O(n^2) time, and an additional O(n^2) for the check function. This is an overall complexity of O(n^4), which will give a TLE. You can optimize the check() function by using a set, map or an unordered map. Thus reducing it to O(n^3 log n) which will pass.
Check my solution : Solution: 35559631 | CodeChef