[ABC225] D - Play Train

[Q] https://atcoder.jp/contests/abc225/tasks/abc225_d

どの電車も、連結が1つしかないルールがとても親切でした。

1. 行のグラフG、戻りのグラフR を作成しますが、要素は1個しかもたないようです。
2. クエリ[3] がきたら、今いる電車からまず先頭を見に行く(R)。
dequeでpush_front()する。
3. お尻まで見る(G)。
dequeでpush_back()する。

Q. 
7 14
1 6 3
1 4 1
1 5 2
1 2 7
1 3 5
3 2
3 4
3 6
2 3 5
2 4 1
1 1 5
3 2
3 4
3 6

1) 1 6 3
G[6] = {3}
R[3] = {6}

2) 1 4 1
G[4] = {1}
R[1] = {4}

...

6) 3 2
・先頭までを調べる。
R[2] = 5
R[5] = 3
R[3] = 6

・おしりまでを調べる。
G[2] = 7

A. 6 3 5 2 7

実装

vector<ll> G[100010];
vector<ll> R[100010];


void dfs1(ll v, deque<ll> &ans){
 for(auto u: G[v]){
   ans.push_back(u);
   dfs1(u, ans);
 }
}

void dfs2(ll v, deque<ll> &ans){
 for(auto u: R[v]){
   ans.push_front(u);
   dfs2(u, ans);
 }
}

int main(){
 cincout();
 
 ll N, Q;
 cin >> N >> Q;
 rep(i, Q){
   ll a, x, y;
   cin >> a >> x;
   if (a==1){
     cin >> y;
     G[x].push_back(y);
     R[y].push_back(x);
   }
   else if (a==2){
     cin >> y;
     G[x].erase(G[x].begin()); // どうせ1個しか入ってない
     R[y].erase(R[y].begin());
   }
   else if (a==3){
     deque<ll> ans;
     ans.push_back(x);
     dfs1(x, ans);
     dfs2(x, ans);
     cout << ans.size() << " ";
     while (!ans.empty()){
       cout << ans.front(); ans.pop_front();
       if (!ans.empty()) cout << " ";
       else cout << endl;
     }
   }
 }
}

https://atcoder.jp/contests/abc225/submissions/26905426