QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#504554#9101. Zayin and BusPlentyOfPenalty#AC ✓311ms8076kbC++202.1kb2024-08-04 13:49:192024-08-04 13:49:21

Judging History

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

  • [2024-08-04 13:49:21]
  • 评测
  • 测评结果:AC
  • 用时:311ms
  • 内存:8076kb
  • [2024-08-04 13:49:19]
  • 提交

answer

#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define rep(i, l, r) for (int i = (l), i##end = (r); i <= i##end; ++i)
#define per(i, l, r) for (int i = (l), i##end = (r); i >= i##end; --i)
#ifdef memset0
#define log(...) fprintf(stderr, __VA_ARGS__)
#else
#define log(...) (void(0))
#define endl '\n'
#endif
using namespace std;
using ll = long long;
using lf = long double;
using ull = unsigned long long;

const int MAXN = 200011;
struct DSU {
  int fa[MAXN];
  void init(int n) {
    for (int i = 1; i <= n; ++i) fa[i] = i;
  }
  int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
  }
  void uni(int x, int y) {
    if (!x || !y) return;
    x = find(x), y = find(y);
    fa[x] = y;
  }
} dsu;
int a[MAXN], n;
vector<int> seq[MAXN];
int it[MAXN], dep[MAXN];
bool check(int lim) {
  // log("check lim = %d\n", lim);
  dsu.init(n + 1);
  for (int i = 1; i <= n; ++i) it[i] = 0;
  for (int i = 1; i <= n; ++i) {
    int d = lim - i - a[i] + 1;
    if (d <= 0) return 0;
    d = min(n, d);
    // log("i=%d,d=%d\n", i, d);
    d = dsu.find(d);
    while (d > 1 && it[d] == seq[d].size()) dsu.uni(d, d - 1), d = dsu.find(d);
    if (it[d] == seq[d].size()) return 0;
    ++it[d];
    if (it[d] == seq[d].size()) dsu.uni(d, d - 1);
  }
  return 1;
}
int main() {
#ifdef memset0
  freopen("A.in", "r", stdin);
#endif
  cin.tie(0)->sync_with_stdio(0);
  int task;
  cin >> task;
  while (task--) {
    // log("new round\n");
    cin >> n;
    for (int i = 1; i <= n; ++i) dep[i] = 0;
    for (int i = 1; i <= n + 1; ++i) seq[i].clear();
    dep[1] = 1, seq[1].emplace_back(1);
    for (int i = 2; i <= n; ++i) {
      int x;
      cin >> x;
      dep[i] = dep[x] + 1;
      seq[dep[i]].emplace_back(i);
    }
    for (int i = 1; i <= n; ++i) cin >> a[i];
    int l = 0, r = 1e9; // temp
    while (l < r) {
      int mid = (l + r) >> 1;
      if (check(mid)) r = mid;
      else
        l = mid + 1;
    }
    cout << l << '\n';
    for (int i = 1; i <= n + 1; ++i) seq[i].clear();
  }
  return 0;
}

詳細信息

Test #1:

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

input:

14
1
1
1
2
1
3
2
1
1 1
2
1
1 2
2
1
2 1
2
1
1 3
2
1
3 1
2
1
1 4
2
1
4 1
3
1 1
1 1 1
3
1 2
1 1 1
3
1 1
1 3 2
3
1 2
1 3 2

output:

2
3
4
3
4
4
5
4
6
5
4
4
6
6

result:

ok 14 lines

Test #2:

score: 0
Accepted
time: 311ms
memory: 8076kb

input:

15
1000
1 2 2 1 1 1 4 8 1 7 7 7 9 3 4 7 15 18 18 4 6 11 19 7 6 1 9 13 2 21 28 6 17 24 24 2 28 5 32 24 23 8 3 26 15 28 25 34 46 41 33 16 46 11 7 2 13 53 12 59 52 53 51 52 31 41 63 18 55 49 55 62 15 19 23 67 18 37 2 4 23 75 58 55 14 84 20 3 7 89 82 15 53 77 60 25 97 69 5 40 54 24 72 10 87 90 99 43 71 ...

output:

98572828
100088663
99870474
100076153
99995412
100076982
99971239
100079684
99928633
100093408
99432584
100093568
99620300
100058966
99565256

result:

ok 15 lines