UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#213848#582. t1FlyfishO2501081ms86476kbC++111.5kb2024-11-13 21:55:482024-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'