#1180235 (C++23) No.3650 Teleportation Cycles

• 問題: No.3650 Teleportation Cycles
• ユーザー: yaaya
• 提出日時: 2026-08-29 05:12:02
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 80 ms / 2,000 ms
• コード長: 2,869 bytes
• コンパイル時間: 3,293 ms
• コンパイル使用メモリ: 354,108 KB
• 実行使用メモリ: 37,548 KB
• 最終ジャッジ日時: 2026-08-29 05:12:13
• 合計ジャッジ時間: 6,472 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

ファイルパターン	結果
sample	AC * 3
other	AC * 36

ソースコード

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,a,b) for(ll i=a-1;i>=b;i--)
#define ll long long
#define ull unsigned ll
#define ld long double
#define bl __int128_t
#define fi first
#define se second
#define vel vector<ll>
#define vvel vector<vel>
#define pll pair<ll,ll>
#define vepll vector<pll>
#define vvepll vector<vepll>
#define ves vector<string>
#define vem vector<mint>
#define vvem vector<vem>
#define pmm pair<mint,mint>
#define cleout(i) cout<<fixed<<setprecision(i)
template<class T>using PQ=priority_queue<T,vector<T>,greater<T>>;
//               上  右 下 左
vector<int> di={-1, 0, 1, 0};
vector<int> dj={ 0, 1, 0,-1};

vector<int> dx={ 0, 1, 0,-1};
vector<int> dy={ 1, 0,-1, 0};


vector<int> ddx={ 1, 1, 1, 0, -1, -1, -1, 0 };
vector<int> ddy={ 1, 0, -1, -1, -1, 0, 1, 1 };

ll inf=1000000000000000000;//1e18
// LLONG_MAX

mt19937_64 rng((ull)chrono::steady_clock::now().time_since_epoch().count());

struct Merge{//a->b
    inline void operator()(vepll &a,vepll &b){
        if(a.size()>b.size()){
            for(pll x:b)a.push_back(x);
            swap(a,b);
        }else{
            for(pll x:a)b.push_back(x);
        }
        return ;
    }
};

template<typename T,typename Merge>
struct UF{
    vel par;
    vvel siz;
    vector<T> val;
    int grp_size;
    Merge merge;
    UF(int N,T id){
        par.assign(N,0);
        siz.assign(N,{});
        val.assign(N,id);
        grp_size=N;
        rep(i,0,N){
            siz[i].push_back(i);
            par[i]=i;
        }
    }
    int root(int x){
        if(par[x]==x)return x;
        par[x]=root(par[x]);
        return par[x];
    }
    void unite(int y,int x){
        int rx=root(x);
        int ry=root(y);
        if(rx==ry) return ;
        grp_size--;
        if(siz[rx].size()>siz[ry].size()){
            for(auto v:siz[ry]){
                siz[rx].push_back(v);
            }
        }else{
            for(auto v:siz[rx]){
                siz[ry].push_back(v);
            }
            swap(siz[rx],siz[ry]);
        }
        siz[ry].clear();
        par[ry]=par[rx];
        merge(val[ry],val[rx]);
    }
    void add(int i,T x){
        merge(x,val[root(i)]);
    }
    T get(ll x){
        return val[root(x)];
    }
    int size(int x){
        return siz[root(x)].size();
    }
    const vel& grp(int x){
        return siz[root(x)];
    }
    bool same(int x,int y){
        return root(x)==root(y);
    }
};

void _solve(){
    ll N;
    cin>>N;
    vel a(N);
    rep(i,0,N)cin>>a[i];
    UF<vepll,Merge> tree(N,{});
    rep(i,0,N){
        a[i]--;
        tree.unite(i,a[i]);
    }
    cout<<tree.grp_size<<"\n";
}


int main(){
    cin.tie(nullptr);
 	ios_base::sync_with_stdio(false);

    
    ll _;
    bool multitest=0;
    if(multitest)cin>>_;
    else _=1;
    rep(__,0,_){
        _solve();
    }
}