QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#253507 | #7626. Quake and Rebuild | ucup-team2307 | WA | 121ms | 3956kb | C++20 | 4.6kb | 2023-11-17 04:06:36 | 2023-11-17 04:06:37 |
Judging History
你现在查看的是最新测评结果
- [2024-11-20 20:27:49]
- hack成功,自动添加数据
- (/hack/1219)
- [2023-12-04 09:28:18]
- hack成功,自动添加数据
- (//qoj.ac/hack/477)
- [2023-11-17 04:06:36]
- 提交
answer
#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
const int B = 512;
struct DSU {
vector<int> e;
DSU(int n) : e(n, -1) {}
int find(int v) { return e[v] < 0 ? v : e[v] = find(e[v]); }
void join(int u, int v) {
u = find(u), v = find(v);
if(u == v) return;
if(u < v) swap(u, v);
e[u] += e[v];
e[v] = u;
}
};
struct Tree {
int n;
vector<int> a, ba, up, up_len;
DSU jump;
Tree(int n) : n(n), a(n), ba(n / B + 1), up(n), up_len(n), jump(n + 1) {}
inline int get_par(int x) {
return max(0, a[x] + ba[x / B]);
}
inline array<int, 2> get_up(int p) {
int par = get_par(p);
if(p / B != par / B)
return {par, 1};
return {up[p], up_len[p]};
}
void read() {
up[0] = 0;
up_len[0] = 0;
for(int i = 1; i < n; i++) {
cin >> a[i], a[i]--;
if((a[i] / B) != (i / B))
up[i] = a[i], up_len[i] = 1;
else {
auto [x, y] = get_up(a[i]);
up[i] = x;
up_len[i] = 1 + y;
}
}
}
inline void sub(int l, int r, int x) {
int p = l;
while(l <= r && (l & (B - 1)))
a[l++] -= x;
for(; l + B - 1 <= r; l += B)
ba[l / B] -= x;
while(l <= r)
a[l++] -= x;
for(p = jump.find(p); p <= r; p = jump.find(p + 1)) {
int par = get_par(p);
if((p / B) != (par / B)) {
jump.join(p, p + 1);
} else {
auto [x, y] = get_up(par);
up[p] = x;
up_len[p] = 1 + y;
}
}
}
};
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, m;
cin >> n >> m;
Tree T(n);
T.read();
vector<vector<int>> ch(n);
vector<int> to_clear, vis(n);
int sum, lca = n;
auto clear = [&]() {
sum = 1;//to account for root
for(auto i : to_clear) {
vis[i] = 0;
ch[i].clear();
}
to_clear = { 0 };
};
auto crawl = [&](int v, int slow) {
int add = 0, chi = -1;
// cout << v << " -->\n";
while(!vis[v]++ && v) {
if(!slow && chi != -1) {
ch[v].push_back(chi);
}
chi = v;
vis[v] = 1;
to_clear.push_back(v);
if(slow) {
v = T.get_par(v);
add++;
} else {
auto [x, y] = T.get_up(v);
v = x;
add += y;
}
}
// cout << v << " " << add << " yay" << endl;
if(!slow && chi != -1) {
ch[v].push_back(chi);
}
return add;
};
auto correct = [&](int v) {
int add = 1;
while(v) {
auto [x, y] = T.get_up(v);
if(vis[v] >= 2)
add = 0;
else
add += y;
v = x;
}
if(vis[v] >= 2) add = 0;
// cout << add << endl;
return add;
};
for(int t, qi = 0; qi < m; qi++) {
cin >> t;
if(t == 1) {
int l, r, x;
cin >> l >> r >> x;
// cout << 1 << " " << l << " " << r << " " << x << endl;
--l, --r;
T.sub(l, r, x);
} else {
int k;
cin >> k;
vector<int> V(k);
for(auto &i : V) cin >> i, i--;
clear();
for(auto i : V)
sum += crawl(i, 0);
// cout << sum << " -\n";
for(int rel = to_clear.size(), i = 0; i < rel; i++) {
int UP = to_clear[i];
// if(ch[UP].size() > 1)
// cout << UP << " " << ch[UP].size() << endl;
for(auto p : ch[UP]) {
sum -= T.get_up(p)[1] - 1;
int U = crawl(T.get_par(p), 1);
// cout << UP << " -> " << p << " " << T.get_par(p) << " " << (T.get_up(p)[1] - 1) << " | " << U << endl;
sum += U;
}
vis[UP] -= ch[UP].size();
}
// cout << sum << " - ";
int lca = 0;
for(auto i : to_clear) if(vis[i] == 1)
lca = max(lca, i);
sum -= correct(V[0]);
cout << sum << '\n';
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3488kb
input:
4 5 1 2 2 2 2 1 4 1 2 3 1 2 3 2 3 4 1 4 4 1 2 2 3 4
output:
3 4 3
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
10 10 1 2 3 3 4 5 7 7 9 1 2 10 3 2 9 9 5 3 10 7 2 4 6 8 1 6 10 3 1 2 7 3 1 7 10 3 2 2 4 3 2 3 7 4 4 1 3 9 3 1 3 9 3 1 10 10 3
output:
10 3 3
result:
ok 3 lines
Test #3:
score: 0
Accepted
time: 121ms
memory: 3708kb
input:
3051 198219 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 4 4 4 1 1 1 6 3 1 1 2 2 2 1 6 3 7 3 3 5 1 2 7 2 5 1 3 4 1 6 2 1 2 1 10 3 3 1 3 2 2 6 3 9 3 1 12 5 1 5 6 7 7 3 2 6 5 8 12 3 7 16 3 9 4 7 1 2 13 3 3 5 9 9 9 6 5 4 41 8 7 10 7 2 7 2 4 14 4 3 1 16 2 6 3 10 3 4 9 10 1 6 1 14 6 10 8 9 6 3 1 1 1 13 22 4 20 17 1 15 ...
output:
78 78 70 64 60 55 60 58 52 54 51 53 56 51 51 57 55 52 49 55 49 50 53 49 49 48 49 48 53 50 50 54 47 52 45 49 49 46 47 48 49 50 48 49 47 48 47 49 48 50 48 49 48 47 49 48 51 48 48 45 45 46 50 50 50 48 49 46 47 47 46 48 48 47 49 47 46 47 46 47 46 45 47 49 49 50 51 48 48 49 47 47 48 50 46 47 48 50 46 47 ...
result:
ok 13214 lines
Test #4:
score: -100
Wrong Answer
time: 96ms
memory: 3956kb
input:
6173 198631 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 ...
output:
2693 1318 1476 1026 1039 5984 267 977 773 887 421 835 171 43 46 593 538 669 567 6046 6087 414 5 352 36 357 6036 374 6136 372 271 83 323 343 34 344 321 6102 5831 277 317 198 273 347 215 6100 16 13 5447 172 7 42 240 204 234 10 24 28 212 198 213 212 218 180 178 235 28 198 136 35 185 24 215 15 197 191 6...
result:
wrong answer 1st lines differ - expected: '2819', found: '2693'