HackerEarth Choose but not both problem solution YASH PAL, 31 July 2024 In this HackerEarth Choose but not both problem solution The alone Y has another array a1,a2,…,an that 1<=ai<=n. this time Y wants to choose some numbers from 1 to n that there is no i that both i and ai is chosen. What is the maximum amount of numbers that Y can choose? HackerEarth Choose but not both problem solution. #include<bits/stdc++.h>using namespace std;typedef long long ll;typedef pair<int, int> ii;const int N = 3e5+100;int f[N];bool mark[N], mark2[N];vector<int> r[N];ii dfs(int v){ mark[v] = true; ii ret = ii(1, 0); for(auto u : r[v]){ if(!mark[u]){ ii cur = dfs(u); ret.second += max(cur.first, cur.second); ret.first += cur.second; } } return ret;}int solve_linear(vector<ii> v){ int ls[2] = {0, 0}; for(auto i : v){ ls[1] += i.second; ls[0] += max(i.first, i.second); swap(ls[0], ls[1]); } return max(ls[0], ls[1]);}int solve(vector<int> cyc){ for(auto i : cyc) mark[i] = true; vector<ii> v; for(auto i : cyc) v.push_back(dfs(i)); if(v.size() == 1) return v[0].second; if(v.size() == 2){ int ret = v[0].first + v[1].second; ret = max(ret, v[0].second + v[1].first); ret = max(ret, v[0].second + v[1].second); return ret; } // 1 is chosen int ret = [&]{ vector<ii> cur; for(int i=3 ; i<v.size() ; i++) cur.push_back(v[i]); return max(v[1].first, v[1].second) + v[0].second + v[2].second + solve_linear(cur); }(); // 1 is not chosen ret = max(ret, [&]{ vector<ii> cur; for(int i=2 ; i<v.size() ; i++) cur.push_back(v[i]); cur.push_back(v[0]); return v[1].second + solve_linear(cur); }()); return ret;}signed main(){ ios_base::sync_with_stdio(false);cin.tie(NULL); int n;cin >> n; for(int i=0 ; i<n ; i++){ cin >> f[i];f[i] --; r[ f[i] ].push_back(i); } int ans=0; for(int i=0 ; i<n ; i++){ if(mark[i]) continue; // finding cycle auto cyc = [&]{ vector<int> cyc; int it = i; while(!mark2[it]){ mark2[it] = true; cyc.push_back(it); it = f[it]; } reverse(cyc.begin(), cyc.end()); while(cyc.back() != it) cyc.pop_back(); return cyc; }(); ans += solve(cyc); } cout << ans << "n";} coding problems