1027D - Mouse Hunt - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;

#define all(a) a.begin(), a.end()
#define PII pair<int, int>
#define fi first
#define sc second
#define LL long long
#define vi vector<int>
#define IO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const int N = 2e5 + 5;
const int M = 2e5 + 5;
const int mod = 998244353;
const int Mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const LL inff = 0x3f3f3f3f3f3f3f3f;
int n, m, k, t, T, _;

PII p[N];
int cnt, sig;
int dfn[N], low[N], vis[N], col[N];
int c[N];
int _c[N];
vector<int> e[N], _e[N];
int in[N];
stack<int> st;

void tarjan(int u){
	dfn[u] = low[u] = ++cnt;

	vis[u] = 1;
	st.push(u);

	for(int i = 0; i < e[u].size(); i++){
		int v = e[u][i];
		if(!dfn[v])	tarjan(v), low[u] = min(low[u], low[v]);
		else if(vis[v])	low[u] = min(low[u], dfn[v]);
	}

	if(dfn[u] == low[u]){
		sig++;
		while(st.size()){
			int x = st.top();	st.pop();
			col[x] = sig;
			_c[sig] = min(_c[sig], c[x]);
			vis[x] = 0;
			if(x == u)	break;
		}
	}
}

void tuopu(){
	LL ans = 0;
	for(int i = 1; i <= sig; i++)
		if(!in[i])	ans += _c[i];
	cout << ans << endl;
}

void solve(){
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> c[i];
	for(int i = 1; i <= n; i++){
		int u = i, v;	cin >> v;
		e[v].push_back(u);
		p[i].fi = u;	p[i].sc = v;
	}

	memset(_c, inf, sizeof _c);

	for(int i = 1; i <= n; i++)
		if(!dfn[i])	tarjan(i);

	LL ans = 0;
	for(int i = 1; i <= n; i++){
		int u = p[i].fi, v = p[i].sc;
		if(col[u] == col[v])	continue;
		_e[col[v]].push_back(col[u]);
		//cout << col[u] << ' ' << col[v] << endl; 
		in[col[u]]++;
	}

	tuopu();
	//cout << sig << ' ' << ans << endl;
}

int main(){
	//for(cin >> _; _--;)
		solve();
	return 0;
}