QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#642424 | #7626. Quake and Rebuild | fryan | WA | 202ms | 3864kb | C++17 | 3.8kb | 2024-10-15 14:08:08 | 2024-10-15 14:08:08 |
Judging History
answer
#pragma once
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
const int mxn = 2e5+5;
const int bsz = 400; //change
const int nbk = 400;
int n,m;
int fa[mxn];
int nx[mxn];
int dx[mxn];
int lz[nbk];
inline int nex(int v) {
if (lz[v/bsz] >= bsz) {
return max(fa[v]+lz[v/bsz],0);
}
return nx[v];
}
inline int dex(int v) {
if (lz[v/bsz] >= bsz) {
return 1;
}
return dx[v];
}
inline void manual_update(int v) {
int f = max(fa[v]+lz[v/bsz],0);
if (f/bsz != v/bsz) {
nx[v] = f;
dx[v] = dx[f]+1;
} else {
nx[v] = nex(f);
dx[v] = 1;
}
}
int lca(int a, int b) {
while (1) {
if (a < b) swap(a,b);
//a > b
int na = nex(a);
int nb = nex(b);
if (na != nb) {
a = na;
} else {
break;
}
}
while (1) {
if (a==b) return a;
if (a < b) swap(a,b);
a = max(fa[a]+lz[a/bsz],0);
}
exit(1);
}
void quake(int l, int r, int d) {
for (int i=l; i%bsz && i<=r; i++) {
fa[i] -= d;
manual_update(i);
}
int lb = (l+bsz-1)/bsz;
int rb = r/bsz-1;
for (int i=lb; i<=rb; i++) {
lz[i] -= d;
if (-lz[i] < bsz) {
//manual update
for (int j=i*bsz; j<(i+1)*bsz; j++) {
manual_update(j);
}
}
}
//do right update
if (r/bsz != l/bsz) {
for (int i=bsz*(r/bsz); i<=r; i++) {
fa[i] -= d;
manual_update(i);
}
}
}
int vis[mxn];
int vnx[mxn];
int ans;
vector<int> proc[nbk];
vector<int> rem, rnx, vcl;
void manual_up(int v) {
int sbk = v/bsz;
while (v/bsz == sbk && !vis[v]) {
vis[v] = 1; rem.push_back(v);
ans++;
v = max(fa[v]+lz[v/bsz],0);
}
}
void rebuild_smart(vector<int> &val) {
rem.clear();
for (int i=0; i<nbk; i++) {
proc[i].clear();
}
sort(all(val));
val.erase(unique(all(val)),val.end());
int RT = val[0];
for (int i=1; i<sz(val); i++) {
RT = lca(RT,val[i]);
}
ans = 1;
vis[RT] = 1;
rem.push_back(RT);
for (int i : val) {
proc[i/bsz].push_back(i);
}
for (int i = (n+bsz-1)/bsz; i>=0; i--) {
rnx.clear(); vcl.clear();
int flag = 0;
for (int v : proc[i]) {
if (vis[v]) continue;
vis[v] = 1;
vcl.push_back(v);
int nxx = nex(v);
vnx[nxx]++;
rnx.push_back(nex(v));
if (vnx[nxx]==2) {flag = 1; break;}
}
if (i == RT/bsz) flag = 1;
for (auto v : rnx) {vnx[v] = 0;}
for (auto v : vcl) {vis[v] = 0;}
if (flag) {
for (int v : proc[i]) {
manual_up(v);
}
} else {
for (int v : proc[i]) {
if (vis[v]) continue;
vis[v] = 1;
ans += dex(v);
proc[i-1].push_back(nex(v));
}
}
}
for (int i : rem) vis[i] = 0;
cout<<ans<<"\n";
}
void rebuild(vector<int> &val) {
set<int> ans;
sort(all(val));
val.erase(unique(all(val)),val.end());
for (int i=0; i<sz(val); i++) {
for (int j=i+1; j<sz(val); j++) {
int R = lca(val[i],val[j]);
int v = val[i];
ans.insert(R);
while (v != R) {
ans.insert(v);
v = max(fa[v]+lz[v/bsz],0);
}
v = val[j];
while (v != R) {
ans.insert(v);
v = max(fa[v]+lz[v/bsz],0);
}
}
}
cout<<sz(ans)<<"\n";
}
signed main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin>>n>>m;
for (int i=1; i<n; i++) {
cin>>fa[i]; --fa[i];
}
//build nx
for (int i=0; i<n; i++) {
if (fa[i]/bsz == i/bsz) {
nx[i] = nx[fa[i]];
dx[i] = dx[fa[i]]+1;
} else {
nx[i] = fa[i];
dx[i] = 1;
}
}
while (m--) {
int t; cin>>t;
// cout<<t<<endl;
if (t==1) {
//quake
int l,r,d; cin>>l>>r>>d;
quake(l-1,r-1,d);
} else {
int k; cin>>k;
vector<int> val;
for (int i=0; i<k; i++) {
int x; cin>>x; --x;
val.push_back(x);
}
// rebuild(val);
// cout<<flush;
rebuild_smart(val);
// cout<<"\n";
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3864kb
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: 3640kb
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: -100
Wrong Answer
time: 202ms
memory: 3704kb
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:
74 86 78 61 65 51 59 50 48 51 44 50 54 46 48 59 58 45 46 47 47 51 56 51 48 47 45 52 52 54 42 58 49 49 46 49 48 46 46 44 50 43 43 44 44 41 46 52 49 48 51 43 46 43 51 47 40 46 45 44 42 47 44 49 42 44 43 45 40 41 45 46 44 45 42 41 46 45 45 49 45 44 48 46 46 48 44 45 45 46 44 43 40 41 43 45 43 39 44 43 ...
result:
wrong answer 1st lines differ - expected: '78', found: '74'