59 lines
1.3 KiB
C++
59 lines
1.3 KiB
C++
|
|
||
|
|
#include <bits/stdc++.h>
|
||
|
|
using namespace std;
|
||
|
|
const int N = 100010;
|
||
|
|
|
||
|
|
struct Node {
|
||
|
|
int id; // 节点编号
|
||
|
|
int L; // 前驱节点下标
|
||
|
|
int R; // 后继节点下标
|
||
|
|
bool deleted = false; // 标记是否被删除
|
||
|
|
} a[N]; // 用数组存储所有节点
|
||
|
|
|
||
|
|
int main() {
|
||
|
|
int n, m;
|
||
|
|
cin >> n;
|
||
|
|
|
||
|
|
// 初始化头节点(0号节点)和尾节点(n+1号节点)
|
||
|
|
a[0] = {0, 0, 1};
|
||
|
|
// 插入第一个节点(编号1)
|
||
|
|
a[1] = {1, 0, n + 1};
|
||
|
|
a[n + 1] = {n + 1, 1, 0};
|
||
|
|
|
||
|
|
// 插入后续节点
|
||
|
|
for (int i = 2; i <= n; i++) {
|
||
|
|
int k, p;
|
||
|
|
cin >> k >> p;
|
||
|
|
a[i].id = i;
|
||
|
|
|
||
|
|
if (p == 1) { // 插入到k的后面
|
||
|
|
a[i].L = k;
|
||
|
|
a[i].R = a[k].R;
|
||
|
|
|
||
|
|
a[a[k].R].L = i; // 注意顺序1
|
||
|
|
a[k].R = i; // 注意顺序2
|
||
|
|
} else { // 插入到k的前面
|
||
|
|
a[i].R = k;
|
||
|
|
a[i].L = a[k].L;
|
||
|
|
|
||
|
|
a[a[k].L].R = i; // 注意顺序1
|
||
|
|
a[k].L = i; // 注意顺序2
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// 处理删除操作
|
||
|
|
cin >> m;
|
||
|
|
while (m--) {
|
||
|
|
int k;
|
||
|
|
cin >> k;
|
||
|
|
a[k].deleted = true;
|
||
|
|
}
|
||
|
|
|
||
|
|
// 遍历链表输出结果
|
||
|
|
for (int c = a[0].R; c != n + 1; c = a[c].R)
|
||
|
|
if (!a[c].deleted)
|
||
|
|
cout << a[c].id << " ";
|
||
|
|
|
||
|
|
return 0;
|
||
|
|
}
|