D問題は苦戦したけど何とか自力で解けた。
http://codeforces.com/contest/513/problem/D2
問題
DFSでpre-order順に1~Nの番号をふった根付バイナリツリーを考える。
ここでC個の情報が与えられる。
各情報では「A[i]番頂点の左or右のサブツリーにB[i]番の頂点が含まれる」という条件が示される。
条件を満たす根付バイナリツリーが存在するなら、それを構築し、in-order順で頂点番号を出力せよ。
解法
F(L,R,MaxR)という再帰関数を考え、F(1,N,N)から初めて再帰的に処理を行っていく。
- L: 現在の頂点番号
- R: Lを頂点としたサブツリーに含まなければならない頂点番号の最大値
- MaxR: Lを頂点としたサブツリーに含んでもよい最大値
F(L,R,MaxR)はLを根とするサブツリーを作った上、そこに含まれる最大の頂点番号Xを返すものとする。
(当然R≦X≦MaxRでなければならない)
頂点Lに対しA[i]=Lとなる条件が存在するとする。
その場合、Lの左側の子になる頂点条件がいくつかある場合、Lの左側の子にはそのような条件のうち最大値MaxLまでを含まなければならない。
F(L+1,MaxL,MaxR)を再帰的に処理したとき、その値をXlとする。
MaxL≦Xl≦MaxRでない場合、条件を満たす木は作れない。
その後Lを出力し、Lの右側のサブツリーとしてF(Xl+1,R,MaxR)を処理して返り値をF(L,R,MaxR)の返り値として返せばよい。
int N,C; vector<int> E[1010000][2]; stringstream S; int dfs(int L,int R,int MR) { if(L>R) return R; sort(E[L][0].begin(),E[L][0].end()); sort(E[L][1].begin(),E[L][1].end()); int LMa=E[L][0].empty()?-1:E[L][0].back(); int RMi=E[L][1].empty()?MR+1:E[L][1][0]; int RMa=E[L][1].empty()?-1:E[L][1].back(); if(LMa>MR || RMa>MR) _P("IMPOSSIBLE\n"), exit(0); int ret=max(L,dfs(L+1,LMa,MR)); if(ret>=RMi) _P("IMPOSSIBLE\n"), exit(0); S << L+1 << " "; return max(ret,dfs(ret+1,max(R,RMa),MR)); } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>C; FOR(i,C) { cin>>x>>y>>s; if(x>=y) return _P("IMPOSSIBLE\n"); E[x-1][s[0]=='R'].push_back(y-1); } dfs(0,N-1,N-1); cout<<S.str()<<endl; }
まとめ
CFは10^6回再帰してもスタック問題ないのね。