题解 CF1152E 【Neko and Flashback】
ljc20020730
2019-04-26 18:55:52
显然对于$b,c$两个数组所描述的数一定是相邻两个数。
也就是说给出这两个数组的目的是告诉选手那两个数是被放在相邻位置的。
对于第$i$组要求,表示数$b_i$和数$c_i$出于相邻位置，于是我们将其建一条无向边。
显然如果构成一组合法的序列，那么这些限制都需要满足，自然想到了欧拉路径（不重复经过所有边）
现在，这条路径上点表示的数就是所求的序列。
于是，我们只需要将点权离散化Fleury跑欧拉路径即可，复杂度大概是O(E)
这里只有$n-1$条边，所以总复杂度是$O(n)$
注意，图可能不是欧拉图，甚至不连通，甚至输入就不合法($a_i > b_i$)在这些情况下直接输出-1即可。
```
# include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int du[N],a[N],b[N],t[N],Path[N],T,n;
vector<int>V[N];
int Ls(int x){return lower_bound(t+1,t+1+T,x)-t;}
int Rl(int x){return t[x];}
void adde(int u,int v)
{
//printf("adde : %d %d\n",u,v);
V[u].push_back(v);
V[v].push_back(u);
du[u]++; du[v]++;
}
void del(int u,int v)
{
//printf("del %d %d\n",u,v);
for (int i=0;i<V[u].size();++i)
if (V[u][i]==v) {
V[u].erase(V[u].begin()+i);
break;
}
for (int i=0;i<V[v].size();++i)
if (V[v][i]==u) {
V[v].erase(V[v].begin()+i);
break;
}
}
void dfs(int u)
{
//printf("u = %d \n",u);
for (int i=0;i<V[u].size();++i) {
int v=V[u][i]; del(u,v); dfs(v);
}
Path[++Path[0]]=u;
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n-1;i++) scanf("%d",&a[i]),t[++t[0]]=a[i];
for (int i=1;i<=n-1;i++) scanf("%d",&b[i]),t[++t[0]]=b[i];
for (int i=1;i<=n-1;i++)
if (a[i]>b[i]) { puts("-1"); return 0;}
sort(t+1,t+1+t[0]);
T=unique(t+1,t+1+t[0])-t-1;
for (int i=1;i<=n-1;i++)
adde(Ls(a[i]),Ls(b[i]));
bool flag=false; int cnt=0;
for (int i=1;i<=n;i++)
if (du[i]%2==1) cnt++;
if (cnt!=0&&cnt!=2) { puts("-1"); return 0;}
for (int i=1;i<=n;i++)
if (du[i]%2==1) { flag=true; dfs(i); break;}
if (flag==false) dfs(1);
if (Path[0]!=n) { puts("-1"); return 0; }
for (int i=1;i<=Path[0];i++)
printf("%d ",Rl(Path[i]));
puts("");
return 0;
}
```