QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#882539 | #4408. 燃烧的呐球 | TulipeNoire | 100 ✓ | 7281ms | 798320kb | C++14 | 8.6kb | 2025-02-05 09:12:00 | 2025-02-05 09:12:01 |
Judging History
answer
#include<bits/stdc++.h>
#define lowbit(x) ((x)&-(x))
using namespace std;
using LL=long long;
using pii=pair<int,int>;
struct Info {
int mn,mpos,se,spos;
inline Info operator+(const int t) {
return {mn+t,mpos,se+t,spos};
}
}INF;
inline Info min(Info x,Info y) {
if (x.mpos==y.mpos) {
if (x.se<y.se) return {min(x.mn,y.mn),x.mpos,x.se,x.spos};
return {min(x.mn,y.mn),x.mpos,y.se,y.spos};
}
if (x.mn<y.mn) {
if (x.se<y.mn) return x;
return {x.mn,x.mpos,y.mn,y.mpos};
}
if (y.se<x.mn) return y;
return {y.mn,y.mpos,x.mn,x.mpos};
}
inline void chkmin(Info &x,Info y) {
x=min(x,y);
}
inline int read() {
int f=0;
char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) f=f*10+(c-'0'),c=getchar();
return f;
}
const int N=1000005,M=100005,inf=1e9;
int n,m,fa[N],qx[M],qy[M];
vector<int>G[N];
int siz[N],tot,dfn[N],efn[N];
struct DSU {
int fa[M];
inline 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]);
}
inline void Merge(int x,int y) {
fa[Find(x)]=Find(y);
}
}D;
void dfs0(int p) {
siz[p]=1,dfn[p]=++tot;
for (auto x:G[p]) dfs0(x),siz[p]+=siz[x];
efn[p]=tot;
}
int dcnt,col[M];
Info ans[M];
inline void solve1() {
Info res=INF;
for (int i=1;i<=m;i++) chkmin(res,{siz[qx[i]]+siz[qy[i]],col[i],inf,0});
for (int i=1;i<=m;i++) ans[i]=res+(siz[qx[i]]+siz[qy[i]]);
}
int nowid;
struct Ops {
int id,pos;
Info origin;
};
struct SGT1 {
Info dat[N<<2];
stack<Ops>stk;
void build(int p,int l,int r) {
dat[p]=INF;
if (l==r) return;
int mid=(l+r)>>1;
build(p<<1,l,mid),build(p<<1|1,mid+1,r);
}
void update(int p,int l,int r,int x,Info d) {
if (nowid) stk.push({nowid,p,dat[p]});
chkmin(dat[p],d);
if (l==r) return;
int mid=(l+r)>>1;
if (x<=mid) update(p<<1,l,mid,x,d);
else update(p<<1|1,mid+1,r,x,d);
}
Info qmin(int p,int l,int r,int L,int R) {
if (L<=l&&r<=R) return dat[p];
int mid=(l+r)>>1;
Info res={inf,0};
if (L<=mid) chkmin(res,qmin(p<<1,l,mid,L,R));
if (R>mid) chkmin(res,qmin(p<<1|1,mid+1,r,L,R));
return res;
}
inline void rollback(int t) {
while (!stk.empty()&&stk.top().id==t) dat[stk.top().pos]=stk.top().origin,stk.pop();
}
}T1x,T1y,T1;
struct SGT2 {
Info tag[N<<2];
stack<Ops>stk;
void build(int p,int l,int r) {
tag[p]={inf,0};
if (l==r) return;
int mid=(l+r)>>1;
build(p<<1,l,mid),build(p<<1|1,mid+1,r);
}
void update(int p,int l,int r,int L,int R,Info d) {
if (L<=l&&r<=R) {
if (nowid) stk.push({nowid,p,tag[p]});
chkmin(tag[p],d);
return;
}
int mid=(l+r)>>1;
if (L<=mid) update(p<<1,l,mid,L,R,d);
if (R>mid) update(p<<1|1,mid+1,r,L,R,d);
}
Info qmin(int p,int l,int r,int x) {
if (l==r) return tag[p];
int mid=(l+r)>>1;
if (x<=mid) return min(tag[p],qmin(p<<1,l,mid,x));
return min(tag[p],qmin(p<<1|1,mid+1,r,x));
}
inline void rollback(int t) {
while (!stk.empty()&&stk.top().id==t) tag[stk.top().pos]=stk.top().origin,stk.pop();
}
}T2x,T2y,T2;
inline void solve2() {
nowid=0,T1x.build(1,1,n),T1y.build(1,1,n),T2x.build(1,1,n),T2y.build(1,1,n);
for (int i=1;i<=m;i++) {
T1x.update(1,1,n,dfn[qx[i]],{-siz[qx[i]]+siz[qy[i]],col[i],inf,0});
T1y.update(1,1,n,dfn[qy[i]],{-siz[qy[i]]+siz[qx[i]],col[i],inf,0});
T2x.update(1,1,n,dfn[qx[i]],efn[qx[i]],{siz[qx[i]]+siz[qy[i]],col[i],inf,0});
T2y.update(1,1,n,dfn[qy[i]],efn[qy[i]],{siz[qx[i]]+siz[qy[i]],col[i],inf,0});
}
for (int i=1;i<=m;i++) {
chkmin(ans[i],T1x.qmin(1,1,n,dfn[qx[i]],efn[qx[i]])+(siz[qx[i]]+siz[qy[i]]));
chkmin(ans[i],T1y.qmin(1,1,n,dfn[qy[i]],efn[qy[i]])+(siz[qx[i]]+siz[qy[i]]));
chkmin(ans[i],T2x.qmin(1,1,n,dfn[qx[i]])+(-siz[qx[i]]+siz[qy[i]]));
chkmin(ans[i],T2y.qmin(1,1,n,dfn[qy[i]])+(-siz[qy[i]]+siz[qx[i]]));
}
}
vector<int>vec[N];
inline void rollback(int p) {
T1.rollback(p),T2.rollback(p);
}
int cnt1,cnt2,rt1[N],rt2[N];
struct Node {
int lc,rc;
Info dat;
}tr1[M<<6],tr2[M<<6];
void update1(int &p,int l,int r,int x,Info d) {
if (!p) p=++cnt1,tr1[p].dat=d;
else chkmin(tr1[p].dat,d);
if (l==r) return;
int mid=(l+r)>>1;
if (x<=mid) update1(tr1[p].lc,l,mid,x,d);
else update1(tr1[p].rc,mid+1,r,x,d);
}
void update2(int &p,int l,int r,int L,int R,Info d) {
if (!p) p=++cnt2,tr2[p].dat=INF;
if (L<=l&&r<=R) {
chkmin(tr2[p].dat,d);
return;
}
int mid=(l+r)>>1;
if (L<=mid) update2(tr2[p].lc,l,mid,L,R,d);
if (R>mid) update2(tr2[p].rc,mid+1,r,L,R,d);
}
int Merge1(int p,int q,int l,int r) {
if (!p||!q) return p+q;
chkmin(tr1[p].dat,tr1[q].dat);
int mid=(l+r)>>1;
tr1[p].lc=Merge1(tr1[p].lc,tr1[q].lc,l,mid);
tr1[p].rc=Merge1(tr1[p].rc,tr1[q].rc,mid+1,r);
return p;
}
int Merge2(int p,int q,int l,int r) {
if (!p||!q) return p+q;
chkmin(tr2[p].dat,tr2[q].dat);
int mid=(l+r)>>1;
tr2[p].lc=Merge2(tr2[p].lc,tr2[q].lc,l,mid);
tr2[p].rc=Merge2(tr2[p].rc,tr2[q].rc,mid+1,r);
return p;
}
Info qmin1(int p,int l,int r,int L,int R) {
if (!p) return INF;
if (L<=l&&r<=R) return tr1[p].dat;
int mid=(l+r)>>1;
Info res=INF;
if (L<=mid) chkmin(res,qmin1(tr1[p].lc,l,mid,L,R));
if (R>mid) chkmin(res,qmin1(tr1[p].rc,mid+1,r,L,R));
return res;
}
Info qmin2(int p,int l,int r,int x) {
if (!p) return INF;
if (l==r) return tr2[p].dat;
int mid=(l+r)>>1;
if (x<=mid) return min(tr2[p].dat,qmin2(tr2[p].lc,l,mid,x));
return min(tr2[p].dat,qmin2(tr2[p].rc,mid+1,r,x));
}
void dfs1(int p) {
nowid=p;
for (auto x:vec[p]) {
T1.update(1,1,n,dfn[qy[x]],{siz[p]-siz[qy[x]],col[x],inf,0});
T2.update(1,1,n,dfn[qy[x]],efn[qy[x]],{siz[p]+siz[qy[x]],col[x],inf,0});
update1(rt1[p],1,n,dfn[qy[x]],{-siz[p]-siz[qy[x]],col[x],inf,0});
update2(rt2[p],1,n,dfn[qy[x]],efn[qy[x]],{-siz[p]+siz[qy[x]],col[x],inf,0});
}
for (auto x:vec[p]) {
chkmin(ans[x],T1.qmin(1,1,n,dfn[qy[x]],efn[qy[x]])+(-siz[p]+siz[qy[x]]));
chkmin(ans[x],T2.qmin(1,1,n,dfn[qy[x]])+(-siz[p]-siz[qy[x]]));
}
for (auto x:G[p]) dfs1(x),rt1[p]=Merge1(rt1[p],rt1[x],1,n),rt2[p]=Merge2(rt2[p],rt2[x],1,n);
rollback(p);
for (auto x:vec[p]) {
chkmin(ans[x],qmin1(rt1[p],1,n,dfn[qy[x]],efn[qy[x]])+(siz[p]+siz[qy[x]]));
chkmin(ans[x],qmin2(rt2[p],1,n,dfn[qy[x]])+(siz[p]-siz[qy[x]]));
}
}
inline void Clear() {
for (int i=1;i<=cnt1;i++) tr1[i]={};
for (int i=1;i<=cnt2;i++) tr2[i]={};
cnt1=cnt2=0;
for (int i=1;i<=n;i++) rt1[i]=rt2[i]=0;
}
inline void solve3() {
Clear(),dfs1(1);
}
inline LL solve() {
for (int i=1;i<=m;i++) col[i]=D.Find(i);
solve1(),solve2(),solve3();
// for (int i=1;i<=m;i++) {
// ans[i]=INF;
// for (int j=1;j<=m;j++) {
// int sum=0;
// if (dfn[qx[i]]<=dfn[qx[j]]&&dfn[qx[j]]<=efn[qx[i]]||dfn[qx[j]]<=dfn[qx[i]]&&dfn[qx[i]]<=efn[qx[j]]) sum+=abs(siz[qx[i]]-siz[qx[j]]);
// else sum+=siz[qx[i]]+siz[qx[j]];
// if (dfn[qy[i]]<=dfn[qy[j]]&&dfn[qy[j]]<=efn[qy[i]]||dfn[qy[j]]<=dfn[qy[i]]&&dfn[qy[i]]<=efn[qy[j]]) sum+=abs(siz[qy[i]]-siz[qy[j]]);
// else sum+=siz[qy[i]]+siz[qy[j]];
// chkmin(ans[i],{sum,col[j],inf,0});
// }
// }
LL sum=0;
// for (int i=1;i<=m;i++) cout<<i<<' '<<col[i]<<' '<<ans[i].se<<' '<<ans[i].spos<<"\n";
for (int i=1;i<=m;i++) if (i!=col[i]) chkmin(ans[col[i]],ans[i]);
for (int i=1;i<=m;i++) {
if (i!=col[i]) continue;
if (ans[i].spos==i) swap(ans[i].mn,ans[i].se),swap(ans[i].mpos,ans[i].spos);
int t=ans[i].spos;
if (D.Find(i)!=D.Find(t)) D.Merge(i,t),sum+=ans[i].se,dcnt--;
}
return sum;
}
inline LL Boruvka() {
LL sum=0;
while (dcnt>1) sum+=solve();
return sum;
}
int main() {
INF={inf,0,inf,-1};
n=read(),dcnt=m=read(),D.init(m),T1.build(1,1,n),T2.build(1,1,n);
for (int i=2;i<=n;i++) G[fa[i]=read()].push_back(i);
dfs0(1);
for (int i=1;i<=m;i++) qx[i]=read(),qy[i]=read(),vec[qx[i]].push_back(i);
printf("%d",Boruvka());
return 0;
}
详细
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 15ms
memory: 77952kb
Test #2:
score: 10
Accepted
time: 16ms
memory: 83944kb
Test #3:
score: 10
Accepted
time: 14ms
memory: 80000kb
Test #4:
score: 10
Accepted
time: 17ms
memory: 80000kb
Test #5:
score: 10
Accepted
time: 14ms
memory: 77956kb
Subtask #2:
score: 10
Accepted
Dependency #1:
100%
Accepted
Test #6:
score: 10
Accepted
time: 1355ms
memory: 333684kb
Test #7:
score: 10
Accepted
time: 740ms
memory: 328860kb
Test #8:
score: 10
Accepted
time: 517ms
memory: 320732kb
Test #9:
score: 10
Accepted
time: 531ms
memory: 329980kb
Test #10:
score: 10
Accepted
time: 683ms
memory: 326476kb
Subtask #3:
score: 10
Accepted
Dependency #2:
100%
Accepted
Test #11:
score: 10
Accepted
time: 2637ms
memory: 365252kb
Test #12:
score: 10
Accepted
time: 1542ms
memory: 360616kb
Test #13:
score: 10
Accepted
time: 1192ms
memory: 354404kb
Test #14:
score: 10
Accepted
time: 1212ms
memory: 359412kb
Test #15:
score: 10
Accepted
time: 1450ms
memory: 358412kb
Subtask #4:
score: 20
Accepted
Test #16:
score: 20
Accepted
time: 520ms
memory: 91972kb
Test #17:
score: 20
Accepted
time: 638ms
memory: 87556kb
Test #18:
score: 20
Accepted
time: 467ms
memory: 89236kb
Test #19:
score: 20
Accepted
time: 485ms
memory: 88812kb
Test #20:
score: 20
Accepted
time: 623ms
memory: 89508kb
Subtask #5:
score: 10
Accepted
Test #21:
score: 10
Accepted
time: 7281ms
memory: 796352kb
Test #22:
score: 10
Accepted
time: 7159ms
memory: 796284kb
Test #23:
score: 10
Accepted
time: 7180ms
memory: 796232kb
Test #24:
score: 10
Accepted
time: 7133ms
memory: 798320kb
Test #25:
score: 10
Accepted
time: 7119ms
memory: 796252kb
Subtask #6:
score: 10
Accepted
Test #26:
score: 10
Accepted
time: 1567ms
memory: 392340kb
Test #27:
score: 10
Accepted
time: 1583ms
memory: 394392kb
Test #28:
score: 10
Accepted
time: 1602ms
memory: 392468kb
Test #29:
score: 10
Accepted
time: 1581ms
memory: 396560kb
Test #30:
score: 10
Accepted
time: 1582ms
memory: 392340kb
Subtask #7:
score: 30
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Dependency #6:
100%
Accepted
Test #31:
score: 30
Accepted
time: 4496ms
memory: 422080kb
Test #32:
score: 30
Accepted
time: 2411ms
memory: 415188kb
Test #33:
score: 30
Accepted
time: 1951ms
memory: 404996kb
Test #34:
score: 30
Accepted
time: 1995ms
memory: 412244kb
Test #35:
score: 30
Accepted
time: 2304ms
memory: 413132kb
Test #36:
score: 30
Accepted
time: 4495ms
memory: 422228kb
Test #37:
score: 30
Accepted
time: 2401ms
memory: 415316kb
Test #38:
score: 30
Accepted
time: 2011ms
memory: 404864kb
Test #39:
score: 30
Accepted
time: 2046ms
memory: 412244kb
Test #40:
score: 30
Accepted
time: 2273ms
memory: 411088kb