QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#504554 | #9101. Zayin and Bus | PlentyOfPenalty# | AC ✓ | 311ms | 8076kb | C++20 | 2.1kb | 2024-08-04 13:49:19 | 2024-08-04 13:49:21 |
Judging History
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