QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#199798	#7347. HDRF	Delay_for_five_minutes^#	WA	1ms	6000kb	C++14	1.7kb	2023-10-04 14:05:55	2023-10-04 14:05:55

Judging History

你现在查看的是最新测评结果

[2023-10-04 14:05:55]
评测

测评结果：WA
用时：1ms
内存：6000kb

查看

[2023-10-04 14:05:55]
提交

answer

#include<bits/stdc++.h>
#define maxn 100005
#define MXVAL 1000000000
int mn[maxn << 2];
int r[maxn];
int dfn[maxn],sz[maxn],cnt,idx[maxn];
int min(int u, int v) {
	if (u == 0 || v == 0) return v + u;

	return r[u] > r[v] ? v : u;
}
void build(int pos,int l,int r) {
	if (l == r) {
		mn[pos] = idx[l];
		return ;
	}
	int mid = (l+r) >> 1;
	build(pos << 1, l, mid);
	build(pos << 1 | 1, mid + 1, r);
	mn[pos] = min(mn[pos << 1], mn[pos << 1 | 1]);
}
int query(int pos,int l,int r,int ql,int qr) {
	if (r < ql || l > qr) return 0;
	if (ql <= l && r <= qr) {
		return mn[pos];
	}
	int mid = (l+r) >> 1;
	return min(query(pos << 1, l, mid, ql, qr),query(pos << 1 | 1, mid + 1, r, ql, qr));
}
void update(int pos,int l,int r,int p) {
	if (l == r) return ;
	int mid = (l+r) >> 1;
	if (p < mid) update(pos << 1, l, mid, p);
	else update(pos << 1 | 1,mid + 1, r, p);
	mn[pos] = min(mn[pos << 1], mn[pos << 1 | 1]);
}
int n;
std::vector<int> G[maxn];
std::vector<int> ans;
void DFS(int u) {
	dfn[u] = ++cnt;
	sz[u] = 1;
	idx[cnt] = u;
	for(auto i : G[u]) {
		DFS(i);
		sz[u] += sz[i];
	}
}
void dfs(int u) {
	r[u] = 1e9 + 1;
	update(1, 1, n, u);
	for(int val = query(1, 1, n, dfn[u],dfn[u] + sz[u] - 1); r[val] <= MXVAL;) {
		dfs(val);
		val = query(1, 1, n, dfn[u],dfn[u] + sz[u] - 1);
	}
	ans.push_back(u);
}
int main() {
	std::ios::sync_with_stdio(0);std::cin.tie(0);
	// freopen("in.txt","r",stdin);
	std::cin >> n;
	for(int i = 2; i <= n; i++) {
		int x;
		std::cin >> x;
		G[x].push_back(i);
	}
	for(int i=1;i<=n;i++) {
		std::cin >> r[i];
	}
	DFS(1);
	// for(int i = 1;i<=n;i++) {
	// 	printf("%d\n",dfn[i]);
	// }
	build(1,1,n);
	dfs(1);
	for(auto i:ans) {
		printf("%d ", i);
	}
	putchar('\n');
}

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 1ms

memory: 6000kb

input:

5
4 4 1 1
3 5 2 1 4

output:

3 2 4 5 1

result:

ok 5 number(s): "3 2 4 5 1"

Test #2:

score: 0

Accepted

time: 0ms

memory: 5924kb

input:

2
1
1 2

output:

2 1

result:

ok 2 number(s): "2 1"

Test #3:

score: -100

Wrong Answer

time: 1ms

memory: 5940kb

input:

100
85 42 34 7 48 48 63 90 37 80 26 50 73 6 11 94 90 41 89 44 9 29 71 44 27 52 27 39 6 91 28 25 63 12 24 23 25 7 19 15 69 84 80 37 28 100 1 78 23 72 15 12 91 90 87 52 13 8 42 51 69 46 20 8 32 5 62 35 13 61 63 7 72 15 37 16 89 34 73 93 71 14 74 65 27 51 81 75 94 57 67 13 40 65 35 63 80 28 78
39 56 6 ...

output:

8 36 24 82 61 43 84 95 79 63 88 93 13 50 55 17 40 19 3 96 26 99 66 32 65 97 27 33 44 71 51 64 20 60 100 49 78 89 56 30 59 74 46 91 6 23 68 62 92 67 5 11 22 42 34 1

result:

wrong answer 1st numbers differ - expected: '95', found: '8'