QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #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
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');
}
Details
Tip: Click on the bar to expand more detailed information
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'