QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#267473 | #7736. Red Black Tree | BoulevardDust | WA | 151ms | 48488kb | C++20 | 3.7kb | 2023-11-27 12:39:46 | 2023-11-27 12:39:47 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define see(x) cerr << x << " "
#define seeln(x) cerr << x << endl
#define out(x) cerr << #x << " = " << x << " "
#define outln(x) cerr << #x << " = " << x << endl
#define re
inline void Rd(int &res){
re char c;res=0;
while(c=getchar(),c<48);
do res=(res<<3)+(res<<1)+(c^48);
while(c=getchar(),c>47);
}
const int N = 100005;
int n;
int col[N];
char str[N];
vector<int> G[N];
struct node {
int src;
int cnt;
int k;
};
const int inf = 1000000000;
int len[N];
int ans[N];
int Log[N];
int vA[N][19], vB[N][19];
void dfs(int x) {
if (G[x].empty()) return (void)(len[x] = 1);
len[x] = inf;
for (int y : G[x]) {
dfs(y);
if (len[y] + 1 < len[x]) {
len[x] = len[y] + 1;
}
}
}
#define sz(x) (int)(x.size())
vector<int> dp[N];
int sum[N];
node src[N];
int calcdp(int x, int id) {
// out(x); out(id); outln(sz(dp[x]));
if (id < 0 || id > len[x]) return inf;
return dp[x][id];
}
int qA(int l, int r) {
int k = Log[r - l + 1];
return min(vA[l][k], vA[r - (1 << k) + 1][k]);
}
int qB(int l, int r) {
int k = Log[r - l + 1];
return min(vB[l][k], vB[r - (1 << k) + 1][k]);
}
void calc_top(int x) {
int y = src[x].src;
int k = src[x].k;
int cnt = src[x].cnt;
// out(x); out(y); out(k); outln(cnt);
dp[x].resize(len[x] + 1);
for (int i = 0; i <= len[x]; ++i) {
dp[x][i] = inf;
vA[i][0] = vB[i][0] = inf;
}
for (int i = 0; i <= len[y] && i <= len[x]; ++i) {
vA[i][0] = dp[y][i] + i;
vB[i][0] = dp[y][i] - i;
}
for (int i = 1; i <= Log[len[x]]; ++i) {
for (int j = 0; j <= len[x] - (1 << i) + 1; ++j) {
vA[j][i] = min(vA[j][i - 1], vA[j + (1 << (i - 1))][i - 1]);
vB[j][i] = min(vB[j][i - 1], vB[j + (1 << (i - 1))][i - 1]);
}
}
for (int i = 0; i <= len[x]; ++i) {
int s1, s2;
s1 = i - min(i, min(k, cnt)), s2 = i - 0;
if (s1 <= s2) {
dp[x][i] = min(dp[x][i], qA(s1, s2) + cnt - i);
}
s1 = i - min(i, k), s2 = i - (cnt + 1);
if (s1 <= s2) {
dp[x][i] = min(dp[x][i], qB(s1, s2) + i - cnt);
}
}
}
node run(int x) {
if (sz(G[x]) == 0) {
ans[x] = 0;
src[x] = (node){x, 0, 0};
dp[x] = {0, 0};
dp[x][col[x] ^ 1] = 1;
// out(x); outln(src[x].src);
return src[x];
}
if (sz(G[x]) == 1) {
ans[x] = ans[G[x][0]];
node tmp = run(G[x][0]);
tmp.k += 1;
tmp.cnt += col[x];
src[x] = tmp;
return tmp;
}
for (int y : G[x]) run(y);
// see("run"); outln(x);
dp[x].resize(len[x] + 1);
for (int i = 0; i <= len[x]; ++i) sum[i] = 0, dp[x][i] = inf;
for (int y : G[x]) {
if (dp[y].empty()) calc_top(y);
for (int i = 0; i <= len[x]; ++i) {
sum[i] = min(sum[i] + calcdp(y, i), inf);
}
}
if (col[x]) {
for (int h = 0; h <= len[x]; ++h) {
int tmp = inf;
tmp = min(tmp, sum[h] + 1);
if (h) tmp = min(tmp, sum[h - 1]);
dp[x][h] = tmp;
}
} else {
for (int h = 0; h <= len[x]; ++h) {
int tmp = inf;
tmp = min(tmp, sum[h]);
if (h) tmp = min(tmp, sum[h - 1] + 1);
dp[x][h] = tmp;
}
}
ans[x] = inf;
for (int i = 0; i <= len[x]; ++i) {
ans[x] = min(ans[x], dp[x][i]);
}
return (node){x, 0, 0};
}
void clear() {
for (int i = 1; i <= n; ++i) G[i].clear(), dp[i].clear();
for (int i = 0; i <= n; ++i) src[i] = (node){0, 0, 0};
}
int main() {
int T; Rd(T); while (T--) {
Rd(n);
scanf("%s", str + 1);
for (int i = 1; i <= n; ++i) col[i] = str[i] - 48;
Log[0] = -1; for (int i = 1; i <= n; ++i) Log[i] = Log[i >> 1] + 1;
for (int i = 2, u; i <= n; ++i) G[Rd(u), u].push_back(i);
dfs(1); run(1);
for (int i = 1; i <= n; ++i) printf("%d%c", ans[i], " \n"[i == n]);
clear();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 14300kb
input:
2 9 101011110 1 1 3 3 3 6 2 2 4 1011 1 1 3
output:
4 1 2 0 0 0 0 0 0 2 0 0 0
result:
ok 2 lines
Test #2:
score: -100
Wrong Answer
time: 151ms
memory: 48488kb
input:
6107 12 000000001000 1 2 3 2 5 4 4 7 3 8 11 19 1100111101111011110 1 2 1 1 4 5 2 4 3 2 2 7 10 2 11 3 15 5 7 0111110 1 1 2 2 1 5 3 000 1 1 7 1000011 1 2 3 3 5 4 7 0001001 1 1 1 3 5 3 8 00111000 1 1 3 2 5 2 7 11 11111110111 1 1 1 4 5 4 5 2 5 1 15 110101101000010 1 2 3 2 1 5 2 5 6 5 8 7 9 14 10 0101000...
output:
0 1 1 1 0 0 0 0 0 0 0 0 6 2 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 1 0 0 0 0 2 1 0 0 0 0 0 0 4 0 0 2 1 0 0 0 0 0 0 4 3 2 0 2 0 0 0 0 0 0 0 0 0 0 2 0 1 0 0 0 0 0 0 0 6 5 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 5 1 0 0 0 5 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 5 3 ...
result:
wrong answer 1st lines differ - expected: '1 1 1 1 0 0 0 0 0 0 0 0', found: '0 1 1 1 0 0 0 0 0 0 0 0'