1872F - Selling a Menagerie - CodeForces Solution

#include <bits/stdc++.h>
#include <chrono>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std::chrono;
using namespace __gnu_pbds;
using namespace std;
#ifndef ONLINE_JUDGE
#include "algo/debug.h"
#else
#define dbg(...) ;
#define debug(...) ;
#define crndl ;
#endif
#define ff first
#define ss second
#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define mii map<int, int>
#define pqb priority_queue<int>
#define pqs priority_queue<int, vi, greater<int>>
#define setbits(x) __builtin_popcountll(x)
#define zrobits(x) __builtin_ctzll(x)
#define modm 1000000007 // this is a prime number
#define inf 1e18
#define ps(x, y) fixed << setprecision(y) << x
#define mk(arr, n, type) type *arr = new type[n];
#define w(x)  \
    int x;    \
    cin >> x; \
    while (x--)
#define fd(i, a, b) for (int i = a; i > b; i--)
#define fde(i, a, b) for (int i = a; i >= b; i--)
#define f(i, a, b) for (int i = a; i < b; i++)
#define fe(i, a, b) for (int i = a; i <= b; i++)
#define input(x) \
    int x;       \
    cin >> x;
#define PI 3.141592653589793238462
#define all(x) (x).begin(), (x).end()
#define endl '\n'
#define el '\n'
#define triplet pair<int, pair<int, int>>
#define prDouble(x) cout << fixed << setprecision(10) << x
#define FastIO                    \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
// #define debug(x)            cerr<<x<<el;
#define set_bits __builtin_popcountll
#define parity __builtin_parity // even number of 1:0 & odd number of 1:1
#define zeroesAtStart __builtin_clz
#define zeroesAtEnd __builtin_ctz
#pragma GCC optimize("O3", "unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") // for optimising popcountll,clz (count leading zeroes)
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
// Custom hash map
struct chash
{
    static uint64_t splitmix64(uint64_t x)
    {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const
    {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
template <class K, class V>
using cmap = gp_hash_table<K, V, chash>;
// example usage: cmap<int, int>
// for map<pair<int,int>,int>
struct HASH
{
    size_t operator()(const pair<int, int> &x) const
    {
        return hash<long long>()(((long long)x.first) ^ (((long long)x.second) << 32));
    }
};
// Operator overloads
template <typename T1, typename T2> // Key should be integer type
using safe_map = unordered_map<T1, T2, chash>;
template <typename T1, typename T2> // cin >> pair<T1, T2>
istream &operator>>(istream &istream, pair<T1, T2> &p)
{
    return (istream >> p.first >> p.second);
}
template <typename T> // cin >> vector<T>
istream &operator>>(istream &istream, vector<T> &v)
{
    for (auto &it : v)
    {
        cin >> it;
    }
    return istream;
}
template <typename T, typename V> // cin >> vector<pair<T,V>>
istream &operator>>(istream &istream, vector<pair<T, V>> &v)
{
    for (auto &it : v)
    {
        cin >> it.ff >> it.ss;
    }
    return istream;
}
template <typename T1, typename T2> // cout << pair<T1, T2>
ostream &operator<<(ostream &ostream, pair<T1, T2> &p)
{
    for (auto x : p)
    {
        cout << x.ff << " " << x.ss << el;
    }
    return (ostream);
}
template <typename T> // cout<< vector<T>
ostream &operator<<(ostream &ostream, vector<T> &v)
{
    for (auto &it : v)
    {
        cout << it << " ";
    }
    return ostream;
}
template <typename T, typename V> // cout << vector<pair<T,V>>
ostream &operator<<(ostream &ostream, vector<pair<T, V>> &v)
{
    for (auto &it : v)
    {
        cout << it.ff << " " << it.ss << el;
    }
    return ostream;
}
//-------------------------------------------------------------------------------------------------------------
//-------------------------------------------------------------------------------------------------------------
// int gcd(int a,int b){ if(b==0) return a; else return gcd(b,a%b); } //time complexity:O(log(max(a,b)))
int gcd(int a, int b)
{
    if (!a || !b)
    {
        return (a | b);
    };
    int shift = zeroesAtEnd(a | b);
    a >>= zeroesAtEnd(a);
    do
    {
        b >>= zeroesAtEnd(b);
        if (a > b)
        {
            swap(a, b);
        }
        b -= a;
    } while (b);
    return (a << shift);
}
vector<int> sieve(int n)
{
    int *arr = new int[n + 1]();
    vector<int> vect;
    for (int i = 2; i <= n; i++)
        if (arr[i] == 0)
        {
            vect.push_back(i);
            for (int j = 2 * i; j <= n; j += i)
                arr[j] = 1;
        }
    return vect;
}
long long expo(int base, int exp, int mod)
{
    int x = 1;
    int i;
    int power = base % mod;
    for (i = 0; i < sizeof(int) * 8; i++)
    {
        int least_sig_bit = 0x00000001 & (exp >> i);
        if (least_sig_bit)
        {
            x = (x * power) % mod;
        }
        power = (power * power) % mod;
    }
    return x;
}
int inv(int a, int b) { return expo(a, b - 2, b); }
int mod_add(int a, int b, int m)
{
    a = a % m;
    b = b % m;
    return (((a + b) % m) + m) % m;
}
int mod_mul(int a, int b, int m)
{
    a = a % m;
    b = b % m;
    return (((a * b) % m) + m) % m;
}
int mod_sub(int a, int b, int m)
{
    a = a % m;
    b = b % m;
    return (((a - b) % m) + m) % m;
}
int mod_div(int a, int b, int m)
{
    a = a % m;
    b = b % m;
    return (mod_mul(a, inv(b, m), m) + m) % m;
} // only for prime m
//-------------------------------------------------------------------------------------------------------------
//-------------------------------------------------------------------------------------------------------------
//-------------------------------------------------------------------------------------------------------------
const int mxN = 1e5 + 5;
vector<int> adj[mxN], adj_rev[mxN];
bool used[mxN];
vector<int> order, component;
vi c;
int indeg[mxN];
void dfs1(int v)
{
    used[v] = true;

    for (auto u : adj[v])
    {
        if (!used[u])
        {
            dfs1(u);
        }
    }

    order.push_back(v);
}

void dfs2(int v)
{
    used[v] = true;
    component.push_back(v);

    for (auto u : adj_rev[v])
        if (!used[u])
            dfs2(u);
}

void solve()
{
    int n;
    cin >> n;
    vi a(n + 1);
    f(i, 1, n + 1) { cin >> a[i]; }
    c.resize(n + 1);
    f(i, 1, n + 1) { cin >> c[i]; }

    f(i, 1, n + 1)
    {
        adj[i].push_back(a[i]);
        adj_rev[a[i]].push_back(i);
        indeg[a[i]]++;
    }

    f(i, 1, n + 1)
    {
        used[i] = false;
    }
    vector<pii> tmp;
    f(i,1,n+1){
        tmp.pb({indeg[i],i});
    }
    sort(all(tmp));

    for(auto ele:tmp)
    {
        int i =ele.ss;
        if (!used[i])
        {
            dfs1(i);
        }
    }

    f(i, 1, n + 1)
    {
        used[i] = false;
    }
    reverse(order.begin(), order.end());
    vector<vi> ans;
    for (auto v : order)
    {
        if (!used[v])
        {
            dfs2(v);
            reverse(all(component));
            int mn = LLONG_MAX, mnNode = 0, pos = 0;
            f(i, 0, component.size())
            {
                int x = component[i];
                if (mn > c[x])
                {
                    mn = c[x];
                    mnNode = x;
                    pos = i;
                }
            }
            pos++;
            vi tmp;
            f(i, pos, component.size())
            {
                tmp.pb(component[i]);
            }
            f(i, 0, pos)
            {
                tmp.pb(component[i]);
            }
            ans.pb(tmp);
            component.clear();
        }
    }
    for (auto x : ans)
    {
        cout << x;
    }
    cout << el;
    order.clear();
    component.clear();
    f(i, 1, n + 1)
    {
        adj_rev[i].clear();
        adj[i].clear();
        indeg[i]=0;
    }
}
int32_t main()
{
    FastIO;
    w(t)
    {
        solve();
    }
    return 0;
}