ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#213853 | #582. t1 | FlyfishO25 | 0 | 957ms | 91740kb | C++11 | 1.6kb | 2024-11-13 22:01:42 | 2024-11-13 23:10:09 |
answer
#include <bits/stdc++.h>
#define int long long
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 << " ";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
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: 23ms
memory: 70848kb
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: 49ms
memory: 70844kb
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: 18ms
memory: 70848kb
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: 45ms
memory: 71040kb
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: 35ms
memory: 71040kb
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: 47ms
memory: 71044kb
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: 197ms
memory: 91740kb
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: 175ms
memory: 91736kb
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: 195ms
memory: 91736kb
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: 173ms
memory: 91736kb
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'