Really confused why my solution TLEs in contest
I solved this question in contest but unfortunately got TLE during contest. I was so confused why it TLEd. After contest I found out the test case which TLEd, b
I solved this question in contest but unfortunately got TLE during contest. I was so confused why it TLEd. After contest I found out the test case which TLEd, but even more surprising when I run the test case in LeetCode console it gets accepted in ~120ms. I am attaching the screenshots as proof. I have submitted this as an issue in LeetCode github but no one responded as today the Contest rating got updated, so posting here for further investigation. @Admin please look into this.\n\nPS:- If someone knows how to tag admin please help me by commenting. \n\nScreenshots:- \n\n![image](https://assets.leetcode.com/users/images/9e157026-661f-4d00-84e7-f9a5a21602de_1631607894.2056518.png)\n![image](https://assets.leetcode.com/users/images/c1bc3094-78d7-41fc-8fea-601d9017dc1c_1631607894.4343064.png)\n![image](https://assets.leetcode.com/users/images/28e42697-3e46-4192-98a9-8e2a878e5229_1631608275.97985.png)\n\n\nCode used:\n\n```cpp\nauto speedup = []() {ios_base::sync_with_stdio(0); cin.tie(nullptr); return 0;}();\n\ntemplate<typename T, bool maximum_mode = false>\nstruct RMQ {\n    int n = 0;\n    vector<T> values;\n    vector<vector<int>> range_low;\n \n    RMQ(const vector<T> &_values = {}) {\n        if (!_values.empty())\n            build(_values);\n    }\n \n    static int highest_bit(int x) {\n        return x == 0 ? -1 : 31 - __builtin_clz(x);\n    }\n \n    // Note: when `values[a] == values[b]`, returns b.\n    int better_index(int a, int b) const {\n        return (maximum_mode ? values[b] < values[a] : values[a] < values[b]) ? a : b;\n    }\n \n    void build(const vector<T> &_values) {\n        values = _values;\n        n = int(values.size());\n        int levels = highest_bit(n) + 1;\n        range_low.resize(levels);\n \n        for (int k = 0; k < levels; k++)\n            range_low[k].resize(n - (1 << k) + 1);\n \n        for (int i = 0; i < n; i++)\n            range_low[0][i] = i;\n \n        for (int k = 1; k < levels; k++)\n            for (int i = 0; i <= n - (1 << k); i++)\n                range_low[k][i] = better_index(range_low[k - 1][i], range_low[k - 1][i + (1 << (k - 1))]);\n    }\n \n    // Note: breaks ties by choosing the largest index.\n    int query_index(int a, int b) const {\n        assert(0 <= a && a < b && b <= n);\n        int level = highest_bit(b - a);\n        return better_index(range_low[level][a], range_low[level][b - (1 << level)]);\n    }\n \n    T query_value(int a, int b) const {\n        return values[query_index(a, b)];\n    }\n};\n \nstruct LCA {\n    int n = 0;\n    vector<vector<int>> adj;\n    vector<int> parent, depth, subtree_size;\n    vector<int> euler, first_occurrence;\n    vector<int> tour_start, tour_end, postorder;\n    vector<int> tour_list, rev_tour_list;\n    vector<int> heavy_root;\n    RMQ<int> rmq;\n    bool built;\n \n    LCA(int _n = 0) {\n        init(_n);\n    }\n \n    // Warning: this does not call build().\n    LCA(const vector<vector<int>> &_adj) {\n        init(_adj);\n    }\n \n    void init(int _n) {\n        n = _n;\n        adj.assign(n, {});\n        parent.resize(n);\n        depth.resize(n);\n        subtree_size.resize(n);\n        first_occurrence.resize(n);\n        tour_start.resize(n);\n        tour_end.resize(n);\n        postorder.resize(n);\n        tour_list.resize(n);\n        heavy_root.resize(n);\n        built = false;\n    }\n \n    // Warning: this does not call build().\n    void init(const vector<vector<int>> &_adj) {\n        init(int(_adj.size()));\n        adj = _adj;\n    }\n \n    void add_edge(int a, int b) {\n        adj[a].push_back(b);\n        adj[b].push_back(a);\n    }\n \n    int degree(int v) const {\n        return int(adj[v].size()) + (built && parent[v] >= 0);\n    }\n \n    void dfs(int node, int par) {\n        parent[node] = par;\n        depth[node] = par < 0 ? 0 : depth[par] + 1;\n        subtree_size[node] = 1;\n \n        // Erase the edge to parent.\n        adj[node].erase(remove(adj[node].begin(), adj[node].end(), par), adj[node].end());\n \n        for (int child : adj[node]) {\n            dfs(child, node);\n            subtree_size[node] += subtree_size[child];\n        }\n \n        // Heavy-light subtree reordering.\n        sort(adj[node].begin(), adj[node].end(), [&](int a, int b) {\n            return subtree_size[a] > subtree_size[b];\n        });\n    }\n \n    int tour, post_tour;\n \n    void tour_dfs(int node, bool heavy) {\n        heavy_root[node] = heavy ? heavy_root[parent[node]] : node;\n        first_occurrence[node] = int(euler.size());\n        euler.push_back(node);\n        tour_list[tour] = node;\n        tour_start[node] = tour++;\n        bool heavy_child = true;\n \n        for (int child : adj[node]) {\n            tour_dfs(child, heavy_child);\n            euler.push_back(node);\n            heavy_child = false;\n        }\n \n        tour_end[node] = tour;\n        postorder[node] = post_tour++;\n    }\n \n    void build(int root = -1, bool build_rmq = true) {\n        parent.assign(n, -1);\n \n        if (0 <= root && root < n)\n            dfs(root, -1);\n \n        for (int i = 0; i < n; i++)\n            if (i != root && parent[i] < 0)\n                dfs(i, -1);\n \n        tour = post_tour = 0;\n        euler.clear();\n        euler.reserve(2 * n);\n \n        for (int i = 0; i < n; i++)\n            if (parent[i] < 0) {\n                tour_dfs(i, false);\n                // Add a -1 in between connected components to help us detect when nodes aren\'t connected.\n                euler.push_back(-1);\n            }\n \n        rev_tour_list = tour_list;\n        reverse(rev_tour_list.begin(), rev_tour_list.end());\n        assert(int(euler.size()) == 2 * n);\n        vector<int> euler_depths;\n        euler_depths.reserve(euler.size());\n \n        for (int node : euler)\n            euler_depths.push_back(node < 0 ? node : depth[node]);\n \n        if (build_rmq)\n            rmq.build(euler_depths);\n \n        built = true;\n    }\n \n    pair<int, array<int, 2>> get_diameter() const {\n        assert(built);\n \n        // We find the maximum of depth[u] - 2 * depth[x] + depth[v] where u, x, v occur in order in the Euler tour.\n        pair<int, int> u_max = {-1, -1};\n        pair<int, int> ux_max = {-1, -1};\n        pair<int, array<int, 2>> uxv_max = {-1, {-1, -1}};\n \n        for (int node : euler) {\n            if (node < 0) break;\n            u_max = max(u_max, {depth[node], node});\n            ux_max = max(ux_max, {u_max.first - 2 * depth[node], u_max.second});\n            uxv_max = max(uxv_max, {ux_max.first + depth[node], {ux_max.second, node}});\n        }\n \n        return uxv_max;\n    }\n \n    // Note: returns -1 if `a` and `b` aren\'t connected.\n    int get_lca(int a, int b) const {\n        a = first_occurrence[a];\n        b = first_occurrence[b];\n \n        if (a > b)\n            swap(a, b);\n \n        return euler[rmq.query_index(a, b + 1)];\n    }\n \n    bool is_ancestor(int a, int b) const {\n        return tour_start[a] <= tour_start[b] && tour_start[b] < tour_end[a];\n    }\n \n    bool on_path(int x, int a, int b) const {\n        return (is_ancestor(x, a) || is_ancestor(x, b)) && is_ancestor(get_lca(a, b), x);\n    }\n \n    int get_dist(int a, int b) const {\n        return depth[a] + depth[b] - 2 * depth[get_lca(a, b)];\n    }\n \n    // Returns the child of `a` that is an ancestor of `b`. Assumes `a` is a strict ancestor of `b`.\n    int child_ancestor(int a, int b) const {\n        assert(a != b);\n        assert(is_ancestor(a, b));\n \n        // Note: this depends on RMQ breaking ties by latest index.\n        int child = euler[rmq.query_index(first_occurrence[a], first_occurrence[b] + 1) + 1];\n        assert(parent[child] == a);\n        assert(is_ancestor(child, b));\n        return child;\n    }\n \n    int get_kth_ancestor(int a, int k) const {\n        while (a >= 0) {\n            int root = heavy_root[a];\n \n            if (depth[root] <= depth[a] - k)\n                return tour_list[tour_start[a] - k];\n \n            k -= depth[a] - depth[root] + 1;\n            a = parent[root];\n        }\n \n        return a;\n    }\n \n    int get_kth_node_on_path(int a, int b, int k) const {\n        int anc = get_lca(a, b);\n        int first_half = depth[a] - depth[anc];\n        int second_half = depth[b] - depth[anc];\n        assert(0 <= k && k <= first_half + second_half);\n \n        if (k < first_half)\n            return get_kth_ancestor(a, k);\n        else\n            return get_kth_ancestor(b, first_half + second_half - k);\n    }\n \n    // Note: this is the LCA of any two nodes out of three when the third node is the root.\n    // It is also the node with the minimum sum of distances to all three nodes (the centroid of the three nodes).\n    int get_common_node(int a, int b, int c) const {\n        // Return the deepest node among lca(a, b), lca(b, c), and lca(c, a).\n        int x = get_lca(a, b);\n        int y = get_lca(b, c);\n        int z = get_lca(c, a);\n        x = depth[y] > depth[x] ? y : x;\n        x = depth[z] > depth[x] ? z : x;\n        return x;\n    }\n \n    // Given a subset of k tree nodes, computes the minimal subtree that contains all the nodes (at most 2k - 1 nodes).\n    // Returns a list of {node, parent} for every node in the subtree. Runs in O(k log k).\n    vector<pair<int, int>> compress_tree(vector<int> nodes) const {\n        if (nodes.empty())\n            return {};\n \n        auto &&compare_tour = [&](int a, int b) { return tour_start[a] < tour_start[b]; };\n        sort(nodes.begin(), nodes.end(), compare_tour);\n        int k = int(nodes.size());\n \n        for (int i = 0; i < k - 1; i++)\n            nodes.push_back(get_lca(nodes[i], nodes[i + 1]));\n \n        sort(nodes.begin() + k, nodes.end(), compare_tour);\n        inplace_merge(nodes.begin(), nodes.begin() + k, nodes.end(), compare_tour);\n        nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());\n        vector<pair<int, int>> result = {{nodes[0], -1}};\n \n        for (int i = 1; i < int(nodes.size()); i++)\n            result.emplace_back(nodes[i], get_lca(nodes[i], nodes[i - 1]));\n \n        return result;\n    }\n};\n\nclass Solution {\npublic:\n    vector<int> ans;\n    vector<int> values;\n    vector<int> pars;\n    int timer = 0;\n    int pos_one;\n    set<int> mex;\n\n    LCA lca;\n\n    void compute(int node) {\n        for(auto u: lca.adj[node]) {\n            if(u != pars[node] && !lca.is_ancestor(u, pos_one)) {\n                compute(u);\n            }\n        }\n        mex.erase(values[node]);\n    }\n\n    vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) {\n        int n = nums.size();\n\n        mex.clear();\n        timer = 0;\n\n        ans.assign(n, 1);\n        for(int i = 1; i <= 100100; i++) {\n            mex.insert(i);\n        }\n\n        lca.init(n);\n\n\n        values = nums;\n        pars = parents;\n\n        for(int i = 1; i < n; i++) {\n            int u = i;\n            int v = parents[u];\n            lca.add_edge(u, v);\n        }\n\n        lca.build();\n\n        auto it = find(nums.begin(), nums.end(), 1);\n        if(it == nums.end()) {\n            return ans;\n        }\n        pos_one = it - nums.begin();\n\n        for(int i = 0; i < n; i++) {\n            if(lca.is_ancestor(pos_one, i)) {\n                mex.erase(nums[i]);\n            }\n        }\n\n        ans[pos_one] = *mex.begin();\n\n        int u = parents[pos_one];\n\n        while(u != -1) {\n            compute(u);\n            ans[u] = *mex.begin();\n            u = parents[u];\n        }\n        \n        return ans;\n    }\n};\n```\n
[]