ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#213848 | #582. t1 | FlyfishO25 | 0 | 1081ms | 86476kb | C++11 | 1.5kb | 2024-11-13 21:55:48 | 2024-11-13 23:09:32 |
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int n;
int psz = 0;
vector<int> G[maxn];
int dfn[maxn];
int sz[maxn];
int a[maxn];
set<int> stc;
map<int, int> mp;
queue<pair<int, int> > Q[maxn];
queue<pair<int, int> > ans; // id, is_stuck
void dfs(int u, int p) {
dfn[u] = ++psz;
sz[u] = 1;
for (auto v : G[u]) {
dfs(v, u);
sz[u] += sz[v];
}
}
void add(int u, int flag) {
int isok = false;
for (int stucked : stc) {
stucked = -stucked;
if (dfn[u] > dfn[stucked] && dfn[u] < dfn[stucked] + sz[stucked]) {
// in stucked subtree
Q[stucked].push(make_pair(u, flag));
isok = true;
break;
}
}
if (flag) stc.insert(-u);
if (!isok) ans.push(make_pair(u, flag));
}
void solve(int u) {
while (!Q[u].empty()) {
auto v = Q[u].front();
Q[u].pop();
if (v.second == 0) {
cout << v.first << " ";
} else {
solve(v.first);
}
}
cout << u << " ";
}
int main() {
cin >> n;
for (int i = 2;i <= n;++i) {
int x;
cin >> x;
G[x].push_back(i);
}
for (int i = 1;i <= n;++i) {
cin >> a[i];
mp[a[i]] = i;
}
dfs(1, 0);
for (int i = 1;i <= n;++i) {
int u = mp[i];
if (G[u].size() == 0) {
add(u, 0);
} else {
add(u, 1);
}
}
int cnt = 0;
while (!ans.empty()) {
auto u = ans.front();
// cout << endl << ++cnt << " " << u.first << " " << u.second << endl;
ans.pop();
if (u.second == 0) {
cout << u.first << " ";
} else {
solve(u.first);
}
}
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 0
Wrong Answer
time: 53ms
memory: 70832kb
input:
100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 ...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 1st numbers differ - expected: '52', found: '0'
Test #2:
score: 0
Wrong Answer
time: 25ms
memory: 70832kb
input:
100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 ...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 1st numbers differ - expected: '97', found: '0'
Test #3:
score: 0
Wrong Answer
time: 31ms
memory: 70828kb
input:
100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 ...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 1st numbers differ - expected: '68', found: '0'
Test #4:
score: 0
Wrong Answer
time: 27ms
memory: 70968kb
input:
1000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 1st numbers differ - expected: '720', found: '0'
Test #5:
score: 0
Wrong Answer
time: 39ms
memory: 70968kb
input:
1000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 1st numbers differ - expected: '993', found: '0'
Test #6:
score: 0
Wrong Answer
time: 25ms
memory: 70968kb
input:
1000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 1st numbers differ - expected: '865', found: '0'
Test #7:
score: 0
Wrong Answer
time: 161ms
memory: 86476kb
input:
100000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 ...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 1st numbers differ - expected: '60966', found: '0'
Test #8:
score: 0
Wrong Answer
time: 163ms
memory: 86468kb
input:
100000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 ...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 1st numbers differ - expected: '73271', found: '0'
Test #9:
score: 0
Wrong Answer
time: 274ms
memory: 86472kb
input:
100000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 ...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 1st numbers differ - expected: '96945', found: '0'
Test #10:
score: 0
Wrong Answer
time: 283ms
memory: 86468kb
input:
100000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 ...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 1st numbers differ - expected: '86618', found: '0'