Official
D - Play Train Editorial by en_translator
It is sufficient to manage the following two values for each train:
- the index of train jointed in front of itself;
- the index of train jointed in back of itself.
For each query of \(c_i = 1,2\), one can update the values above in an \(O(1)\) time.
For each query of \(c_i = 3\), one can process it with a naive implementation, due to the constraints that “the sum of numbers of indices of trains to output is at most \(10^6\).”
Therefore, the problem has been solved.
A sample code in C++ follows.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
signed main(){
ll n,q;cin>>n>>q;
ll nil=-1;
vector<ll>front(n+1,nil); // front[i] := The train jointed in front of Train i, or nil if there's no such train.
vector<ll>back(n+1,nil); // back[i] := The train jointed in back of Train i, or nil if there's no such train.
while(q--){
ll c;cin>>c;
if(c==1){
ll x,y;cin>>x>>y;
back[x] = y;
front[y] = x;
}else if(c==2){
ll x,y;cin>>x>>y;
back[x] = nil;
front[y] = nil;
}else{
ll x;cin>>x;
while(front[x] != nil){
x = front[x]; // Move to the first of the connected component of x
}
vector<ll>ans;
while(x != nil){
ans.push_back(x);
x = back[x];
}
cout<<ans.size()<<" ";
for(ll i=0;i<=(int)ans.size()-1;i++){
cout<<ans[i];
if(i!=(int)ans.size()-1)cout<<" ";
else cout<<endl;
}
}
}
return 0;
}
posted:
last update: