gotutiyan’s blog

競技プログラミングをやったりopenframeworksでお絵かきをしたりしています。

AOJ Amida, the City of Miracle 解説

問題
Amida, the City of Miracle | Aizu Online Judge


解説
あみだくじの問題です。
あみだくじ系の問題では、最初、i番目には番号iが繋がっていますが、横棒が追加されるたびに繋がる先が入れ替わると考えることができます。

例えば最初、縦棒1 2 3 4 5には番号1 2 3 4 5が繋がっていますが、2と3を繋ぐ横棒が現れた瞬間、番号1 3 2 4 5に繋がることになります。
この方法では、横棒の深さが浅い順に処理する必要がありますが、今回は深さが浅い順に与えられるとは限りません。そこで、一度深さでソートしてから処理を始める必要があります。

このために、vector< pair< int, pair< int,int>>> v;として、pairを入れ子にすることを考えます。1つ目のpairのsecond要素にさらにpairが来ます。
pairはsort()関数でソートしたとき、first要素を優先してソートされます。

これにより、配列の中身は以下のようになります。
v[I].first 階層
v[I].second.first 横棒の始点
v[I].second.second 横棒の終点

入力を受けてソートした後、前から順にans[横棒の始点-1] と ans[横棒の終点-1] を交換していけば、正解にたどり着けます。
始点と終点は1オリジン、配列の要素は0オリジンであることに注意です。

#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++)
#define Sort(x) sort((x).begin(),(x).end())
 
using namespace std;
 
int main(){
    while(1){
    int n,m,a;
    cin>>n>>m>>a;
    if(n==0&&m==0&&a==0)break;
    vector<int> ans(n);
    rep(i,0,n)ans[i]=i+1; //最初は横棒i は番号i に繋がる(オリジンの違いに注意)
     
    vector<pair<int,pair<int,int>>> v(m);
    rep(i,0,m){
        cin>>v[i].first>>v[i].second.first>>v[i].second.second; //入力
    }
     
    Sort(v); //階層順にソート
    rep(i,0,m){
        swap(ans[v[i].second.first-1],ans[v[i].second.second-1]); //階層の浅い順に繋がる先を交換
    }
    cout<<ans[a-1]<<endl; //a番目の縦棒につながる数字を出力
    }
    return 0;
}