QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#293840#7736. Red Black Treeucup-team859#WA 347ms143264kbC++142.3kb2023-12-29 20:45:072023-12-29 20:45:07

Judging History

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

  • [2024-02-19 10:14:05]
  • hack成功,自动添加数据
  • (/hack/538)
  • [2023-12-29 20:45:07]
  • 评测
  • 测评结果:WA
  • 用时:347ms
  • 内存:143264kb
  • [2023-12-29 20:45:07]
  • 提交

answer

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

const int maxN = 100005;

struct graph {
  long long a, b;
  priority_queue<long long> *pq;

  graph operator+(graph aux) {
    graph sum;

    sum.a = a + aux.a;
    sum.b = b + aux.b;

    if (pq->size() < aux.pq->size()) {
      sum.pq = aux.pq;

      while (!pq->empty()) {
        sum.pq->push(pq->top());
        pq->pop();
      }
    } else {
      sum.pq = pq;

      while (!aux.pq->empty()) {
        sum.pq->push(aux.pq->top());
        aux.pq->pop();
      }
    }

    return sum;
  }
};
graph d[maxN];

int n;
int P[maxN], C[maxN], ans[maxN];

void solve() {
  cin >> n;
  vector<bool> frunza(n + 1, 1);
  vector<graph> d(n + 1);
  vector<int> P(n + 1), C(n + 1), ans(n + 1, 0);
  string str;
  cin >> str;
  for (int i = 1; i <= n; i++) {
    C[i] = str[i - 1] - '0';
  }
  for (int i = 2; i <= n; i++) {
    cin >> P[i];
    frunza[P[i]] = 0;
  }
  for (int i = 1; i <= n; i++) {
    d[i].pq = new priority_queue<long long>;
  }
  for (int i = n; i > 1; --i) {
    if (frunza[i]) {
      d[i].a = 1;
      d[i].b = -C[i];

      d[i].pq->push(C[i]);
      d[i].pq->push(C[i]);
      d[i].pq->push(C[i]);
      d[i].pq->push(C[i]);
      d[i].pq->push(C[i]);
      d[i].pq->push(C[i]);
      d[i].pq->push(C[i]);
      d[i].pq->push(C[i]);

      d[P[i]] = d[P[i]] + d[i];
      continue;
    }
    while (d[i].a > 1) {
      --d[i].a;
      d[i].b += d[i].pq->top();
      d[i].pq->pop();
    }
    ans[i] = d[i].b + d[i].pq->top();
    long long x, y;
    x = d[i].pq->top();
    d[i].pq->pop();
    y = d[i].pq->top();
    d[i].pq->pop();

    d[i].pq->push(x + C[i]);
    d[i].pq->push(y + C[i]);

    d[i].b -= C[i];

    d[P[i]] = d[P[i]] + d[i];
  }
  while (d[1].a > 0) {
    --d[1].a;
    d[1].b += d[1].pq->top();
    d[1].pq->pop();
  }
  ans[1] = d[1].b;
  for (int i = 1; i <= n; i++) {
    cout << ans[i];
    if (i != n) {
      cout << ' ';
    }
  }
  cout << '\n';
}

int main() {
#ifdef LOCAL
  freopen("test.in", "r", stdin);
  freopen("test.out", "w", stdout);
#endif // LOCAL
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);

  int t = 1;
  cin >> t;
  while (t--) {
    solve();
  }

  return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5492kb

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: 347ms
memory: 143264kb

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:

3 3 2 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 0 0 2 0 0 0 0 0 0 0 0 0 0
2 0 2 0 0 0 0 0 0 0
8 7 0 2 0 0 0 0 0 0 0 1 0 0 0 0 0
1 1 0 0 0
4 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
7 5 ...

result:

wrong answer 1st lines differ - expected: '1 1 1 1 0 0 0 0 0 0 0 0', found: '3 3 2 1 0 0 0 0 0 0 0 0'