UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#213865#582. t1one_zero_four_zero6030ms3648kbC++11873b2024-11-13 22:56:212024-11-13 23:11:10

answer

#include<bits/stdc++.h>
using namespace std;

int N, cnt = 0;
int fa[100005];
vector<int> E[100005];
int r[100005], val[100005];
bool vis[100005];
int son[100005];

void dfs(int u){
	son[u] = -1;
	for (auto && v : E[u]){
		if (vis[v]) continue;
		dfs(v);
		if (r[v] < r[u]){
			son[u] = v;
			r[u] = r[v];
		}
	}
	r[u] = min(r[u], val[u]);
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("../data.in", "r", stdin);
	freopen("../data.out", "w", stdout);
#endif

	scanf("%d", &N);
	for (int i = 2; i <= N; i ++){
		scanf("%d", &fa[i]);
		E[fa[i]].push_back(i);
	}
	for (int i = 1; i <= N; i ++){
		scanf("%d", &val[i]);
	}
	while (cnt < N){
		memset(r, 0x3f, 4 * N + 10);
		dfs(1);
		int pos = 1;
		while (son[pos] != -1){
			pos = son[pos];
		}
		printf("%d ", pos);
		vis[pos] = 1;
		cnt ++;
	}
	printf("\n");

	return 0;
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 2ms
memory: 3600kb

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:

52 75 61 96 94 85 99 65 92 64 100 53 79 67 84 89 69 62 88 58 87 68 51 76 56 70 74 55 91 72 59 82 71 ...

result:

ok 100 numbers

Test #2:

score: 10
Accepted
time: 0ms
memory: 3604kb

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:

97 98 56 64 88 71 85 54 94 81 69 74 77 82 66 76 100 95 78 57 93 86 80 83 63 90 68 99 53 52 73 91 96 ...

result:

ok 100 numbers

Test #3:

score: 10
Accepted
time: 0ms
memory: 3600kb

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:

68 100 83 82 66 57 73 90 74 89 92 84 78 52 99 65 75 54 71 87 85 77 61 93 72 63 64 58 60 69 91 96 67 ...

result:

ok 100 numbers

Test #4:

score: 10
Accepted
time: 11ms
memory: 3644kb

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:

720 630 795 982 858 778 764 843 958 636 655 718 999 640 819 553 685 815 801 611 580 660 848 722 508 ...

result:

ok 1000 numbers

Test #5:

score: 10
Accepted
time: 7ms
memory: 3648kb

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:

993 967 945 661 760 801 836 832 798 725 609 708 916 659 785 955 912 802 778 739 850 529 680 664 847 ...

result:

ok 1000 numbers

Test #6:

score: 10
Accepted
time: 10ms
memory: 3644kb

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:

865 829 713 826 804 598 835 729 919 613 859 604 586 677 926 808 871 883 512 573 946 688 540 980 501 ...

result:

ok 1000 numbers

Test #7:

score: 0
Time Limit Exceeded

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:


result:


Test #8:

score: 0
Time Limit Exceeded

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:


result:


Test #9:

score: 0
Time Limit Exceeded

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:


result:


Test #10:

score: 0
Time Limit Exceeded

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:


result: