Codeforces Book

Debugging Help
#1

Problem Info

Codeforces Book

My Work

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <tuple>
#include <numeric>
#include <climits>
 
using namespace std;
 
//change the long long to int if you need to save memory/time really badly
typedef long long ll;
 
//Comment this define when working on interactive problems
#define endl "\n"
 
const ll MAXN = 2e5 + 1;
const ll ZER = 0;
const ll ONE = 1;
const ll INF = INT_MAX;
const ll NINF = INT_MIN;
const ll MOD = 1e9 + 7;

void solve()
{
    ll n;
    cin >> n;
    
    vector<ll> adj[MAXN];
    ll in[MAXN]; //stores in-degree of a node
    
    for (ll i = 0; i < n; i++) {
        ll k;
        cin >> k;
            
        in[i] = k;
        
        while (k--) {
            ll a;
            cin >> a;
            
            adj[a - 1].push_back(i);
        }
        
        sort(adj[i].begin(), adj[i].end());
    }
    
    queue<ll> nodes;
    bool visited[n];
    for (ll i = 0; i < n; i++) {
        if (in[i] == 0) {
            nodes.push(i);
        }
        
        visited[i] = false;
    }
    
    vector<ll> order;
    while (!nodes.empty()) {
        ll cur = nodes.front();
        nodes.pop();
        
        if (visited[cur]) {
            continue;
        }
        
        visited[cur] = true;
        order.push_back(cur);
        
        ll ind = lower_bound(adj[cur].begin(), adj[cur].end(), cur) - adj[cur].begin();
        if (ind == adj[cur].size()) {
            ind = 0;
        }
        
        for (ll i = 0; i < adj[cur].size(); i++) {
            ll tind = (ind + i) % adj[cur].size();
            in[adj[cur][tind]]--;
            
            if (in[adj[cur][tind]] == 0) {
                nodes.push(adj[cur][tind]);
            }
        }
        
        
    }
 
    for (ll i = 0; i < n; i++) {
        if (!visited[i]) {
            cout << -1 << endl;
            return;
        }
    }
    
    ll ans = 1;
    for (ll i = 1; i < order.size(); i++) {
        if (order[i] < order[i - 1]) {
            ans++;
        }
    }
    
    cout << ans << endl;
    
    return;
}
 
 
int main()
{
    //Fast IO
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
     
    ll t;
    cin >> t;
    //t = 1;
    
 
    while (t--) {
        solve();
    }
    
}

I though that the time complexity is nlogn but it TLE’s when I submitted the code. Can someone help me anaylze the time complexity of this code?

#3

You’re initializing 2\cdot 10^5 vectors each time you call the solve() function. That might be the problem.