QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#557421 | #4408. 燃烧的呐球 | DaiRuiChen007 | 100 ✓ | 4426ms | 606828kb | C++17 | 6.9kb | 2024-09-11 09:36:57 | 2024-09-11 09:36:57 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5,MAXM=1e5+5,inf=1e9;
vector <int> G[MAXN],qx[MAXN],qy[MAXN];
int fa[MAXN],siz[MAXN],id[MAXN],dcnt,L[MAXN],R[MAXN];
int n,m,col[MAXN],X[MAXN],Y[MAXN];
vector <int> dfn,rdfn,eul;
long long ans=0;
inline void dfs(int u) {
L[u]=id[u]=++dcnt,siz[u]=1;
dfn.push_back(u),eul.push_back(u);
for(int v:G[u]) dfs(v),siz[u]+=siz[v];
R[u]=dcnt;
rdfn.push_back(u),eul.push_back(-u);
}
struct E {
int v,w;
E(int x=0,int c=inf): v(x),w(c) {}
inline friend bool operator==(E x,E y) { return x.v==y.v; }
inline friend bool operator <(E x,E y) { return x.w<y.w; }
};
struct I {
E mn1,mn2;
I(int x=0,int c=inf): mn1(x,c),mn2(0,inf) {}
inline I operator +=(I oth) {
if(oth.mn1<mn1) swap(oth.mn1,mn1),swap(oth.mn2,mn2);
mn2=min(mn2,oth.mn1==mn1?oth.mn2:oth.mn1);
return *this;
}
inline I operator +=(int oth) {
mn1.w+=oth,mn2.w+=oth;
return *this;
}
inline I operator +(I oth) const {
I tmp(*this);
return tmp+=oth;
}
inline I operator +(int oth) const {
I tmp(*this);
return tmp+=oth;
}
};
struct D {
int id;
I val;
D(int i=0,I v=I()): id(i),val(v) {}
};
I r[MAXN];
namespace Case1 { //out,out
inline void main() {
I now;
for(int i=1;i<=m;++i) now+=I(col[i],siz[X[i]]+siz[Y[i]]);
for(int i=1;i<=m;++i) r[i]+=now+(siz[X[i]]+siz[Y[i]]);
}
}
namespace Case2 { //son,out
I minx[MAXN],miny[MAXN];
inline void main() {
for(int i=1;i<=n;++i) minx[i]=miny[i]=I();
for(int u:rdfn) {
for(int i:qx[u]) minx[u]+=I(col[i],siz[Y[i]]-siz[X[i]]);
for(int i:qy[u]) miny[u]+=I(col[i],siz[X[i]]-siz[Y[i]]);
for(int v:G[u]) minx[u]+=minx[v],miny[u]+=miny[v];
for(int i:qx[u]) r[i]+=minx[u]+(siz[Y[i]]+siz[X[i]]);
for(int i:qy[u]) r[i]+=miny[u]+(siz[X[i]]+siz[Y[i]]);
}
}
}
namespace Case3 { //fa,out
I minx[MAXN],miny[MAXN];
inline void main() {
for(int i=1;i<=n;++i) minx[i]=I(),miny[i]=I();
for(int u:dfn) {
for(int i:qx[u]) minx[u]+=I(col[i],siz[X[i]]+siz[Y[i]]);
for(int i:qy[u]) miny[u]+=I(col[i],siz[Y[i]]+siz[X[i]]);
for(int v:G[u]) minx[v]+=minx[u],miny[v]+=miny[u];
for(int i:qx[u]) r[i]+=minx[u]+(siz[Y[i]]-siz[X[i]]);
for(int i:qy[u]) r[i]+=miny[u]+(siz[X[i]]-siz[Y[i]]);
}
}
}
namespace Case4 { //son son
struct SegmentTree {
struct Node {
int ls,rs;
I min;
} tr[MAXM*24];
int tot;
inline void ins(int u,I k,int l,int r,int &p) {
if(!p) tr[p=++tot]={0,0,I()}; tr[p].min+=k;
if(l==r) return ;
int mid=(l+r)>>1;
if(u<=mid) ins(u,k,l,mid,tr[p].ls);
else ins(u,k,mid+1,r,tr[p].rs);
}
inline I qry(int ul,int ur,int l,int r,int p) {
if(!p||ul>ur) return I();
if(ul<=l&&r<=ur) return tr[p].min;
int mid=(l+r)>>1;
if(ur<=mid) return qry(ul,ur,l,mid,tr[p].ls);
if(mid<ul) return qry(ul,ur,mid+1,r,tr[p].rs);
return qry(ul,ur,l,mid,tr[p].ls)+qry(ul,ur,mid+1,r,tr[p].rs);
}
inline void merge(int l,int r,int q,int &p) {
if(!p||!q) return p+=q,void();
tr[p].min+=tr[q].min;
if(l==r) return ;
int mid=(l+r)>>1;
merge(l,mid,tr[q].ls,tr[p].ls),merge(mid+1,r,tr[q].rs,tr[p].rs);
}
} T;
int rt[MAXN];
inline void main() {
T.tot=0;
for(int i=1;i<=n;++i) rt[i]=0;
for(int u:rdfn) {
for(int i:qx[u]) T.ins(id[Y[i]],I(col[i],-siz[X[i]]-siz[Y[i]]),1,n,rt[u]);
for(int v:G[u]) T.merge(1,n,rt[v],rt[u]);
for(int i:qx[u]) r[i]+=T.qry(L[Y[i]],R[Y[i]],1,n,rt[u])+(siz[X[i]]+siz[Y[i]]);
}
}
}
namespace Case5 { //fa,son
D stk[MAXM*24];
int tp;
struct SegmentTree {
static const int N=1<<20;
I tr[N<<1];
inline void upd(int x,I z) {
x+=N,stk[++tp]=D(x,tr[x]),tr[x]+=z;
for(x>>=1;x;x>>=1) stk[++tp]=D(x,tr[x]),tr[x]+=z;
}
inline I qry(int l,int r) {
I g=I();
for(l+=N-1,r+=N+1;l^r^1;l>>=1,r>>=1) {
if(!(l&1)) g+=tr[l^1];
if(r&1) g+=tr[r^1];
}
return g;
}
} T;
int lst[MAXN];
inline void main() {
for(int u:eul) {
if(u>0) {
lst[u]=tp;
for(int i:qx[u]) T.upd(id[Y[i]],I(col[i],siz[X[i]]-siz[Y[i]]));
for(int i:qx[u]) r[i]+=T.qry(L[Y[i]],R[Y[i]])+(siz[Y[i]]-siz[X[i]]);
} else {
u*=-1;
while(tp>lst[u]) T.tr[stk[tp].id]=stk[tp].val,--tp;
}
}
for(int u:eul) {
if(u>0) {
lst[u]=tp;
for(int i:qy[u]) T.upd(id[X[i]],I(col[i],siz[Y[i]]-siz[X[i]]));
for(int i:qy[u]) r[i]+=T.qry(L[X[i]],R[X[i]])+(siz[X[i]]-siz[Y[i]]);
} else {
u*=-1;
while(tp>lst[u]) T.tr[stk[tp].id]=stk[tp].val,--tp;
}
}
}
}
namespace Case6 { //fa,fa
int hson[MAXN],top[MAXN];
inline void dfs(int u,int rt) {
top[u]=rt;
for(int v:G[u]) if(siz[v]>siz[hson[u]]) hson[u]=v;
if(hson[u]) dfs(hson[u],rt);
for(int v:G[u]) if(v^hson[u]) dfs(v,v);
}
D stk1[MAXM*24],stk2[MAXM];
int tp1,tp2;
struct BalanceTree {
int ls[MAXN],rs[MAXN],f[MAXN];
I w[MAXN],mx[MAXN];
inline void build() {
for(int s=1;s<=n;++s) if(top[s]==s) {
vector <int> ci;
for(int u=s;u;u=hson[u]) ci.push_back(u);
function<int(int,int)> link=[&](int x,int y) {
if(x>y) return 0;
int all=0,tsiz=0;
for(int i=x;i<=y;++i) all+=siz[ci[i]]-siz[hson[ci[i]]];
for(int i=x;i<=y;++i) {
tsiz+=siz[ci[i]]-siz[hson[ci[i]]];
if(tsiz>all/2) {
int p=ci[i];
ls[p]=link(x,i-1),rs[p]=link(i+1,y);
if(ls[p]) f[ls[p]]=p;
if(rs[p]) f[rs[p]]=p;
return p;
}
}
return -1;
};
f[link(0,ci.size()-1)]=fa[s];
}
}
inline void upd(int x,I z) {
stk2[++tp2]=D(x,w[x]),w[x]+=z;
for(;x;x=f[x]) {
stk1[++tp1]=D(x,mx[x]),mx[x]+=z;
if(x!=ls[f[x]]&&x!=rs[f[x]]) break;
}
}
inline I qry(int x) {
I g=w[x]+mx[ls[x]];
for(;f[x];x=f[x]) if(x!=ls[f[x]]) g+=w[f[x]]+mx[ls[f[x]]];
return g;
}
} T;
inline void init() { dfs(1,1),T.build(); }
int lst1[MAXN],lst2[MAXN];
inline void main() {
for(int u:eul) {
if(u>0) {
lst1[u]=tp1,lst2[u]=tp2;;
for(int i:qx[u]) T.upd(Y[i],I(col[i],siz[X[i]]+siz[Y[i]]));
for(int i:qx[u]) r[i]+=T.qry(Y[i])+(-siz[X[i]]-siz[Y[i]]);
} else {
u*=-1;
while(tp1>lst1[u]) T.mx[stk1[tp1].id]=stk1[tp1].val,--tp1;
while(tp2>lst2[u]) T.w[stk2[tp2].id]=stk2[tp2].val,--tp2;
}
}
}
}
inline int find(int x) { while(x^col[x]) x=col[x]=col[col[x]]; return x; }
inline void boruvka() {
for(int i=1;i<=m;++i) r[i]=I();
Case1::main(),Case2::main(),Case3::main();
Case4::main(),Case5::main(),Case6::main();
vector <array<int,3>> cur;
for(int i=1;i<=m;++i) if(i^col[i]) r[col[i]]+=r[i];
for(int i=1;i<=m;++i) if(i==col[i]) {
E e=(r[i].mn1.v==col[i])?r[i].mn2:r[i].mn1;
cur.push_back({i,e.v,e.w});
}
for(auto i:cur) if(find(i[0])^find(i[1])) col[find(i[0])]=find(i[1]),ans+=i[2];
}
inline bool judge() {
int cnt=0;
for(int i=1;i<=m;++i) col[i]=find(i),cnt+=(i==col[i]);
return cnt>1;
}
signed main() {
scanf("%d%d",&n,&m);
for(int i=2;i<=n;++i) scanf("%d",&fa[i]),G[fa[i]].push_back(i);
dfs(1);
Case6::init();
for(int i=1;i<=m;++i) {
scanf("%d%d",&X[i],&Y[i]),col[i]=i;
qx[X[i]].push_back(i);
qy[Y[i]].push_back(i);
}
while(judge()) boruvka();
printf("%lld\n",ans);
return 0;
}
Details
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 31ms
memory: 371224kb
Test #2:
score: 10
Accepted
time: 28ms
memory: 377108kb
Test #3:
score: 10
Accepted
time: 23ms
memory: 380592kb
Test #4:
score: 10
Accepted
time: 28ms
memory: 382864kb
Test #5:
score: 10
Accepted
time: 24ms
memory: 374660kb
Subtask #2:
score: 10
Accepted
Dependency #1:
100%
Accepted
Test #6:
score: 10
Accepted
time: 1751ms
memory: 463392kb
Test #7:
score: 10
Accepted
time: 1193ms
memory: 461168kb
Test #8:
score: 10
Accepted
time: 803ms
memory: 455808kb
Test #9:
score: 10
Accepted
time: 794ms
memory: 459828kb
Test #10:
score: 10
Accepted
time: 1180ms
memory: 459872kb
Subtask #3:
score: 10
Accepted
Dependency #2:
100%
Accepted
Test #11:
score: 10
Accepted
time: 2649ms
memory: 465104kb
Test #12:
score: 10
Accepted
time: 1868ms
memory: 462828kb
Test #13:
score: 10
Accepted
time: 1285ms
memory: 457088kb
Test #14:
score: 10
Accepted
time: 1309ms
memory: 461472kb
Test #15:
score: 10
Accepted
time: 1748ms
memory: 460708kb
Subtask #4:
score: 20
Accepted
Test #16:
score: 20
Accepted
time: 185ms
memory: 385280kb
Test #17:
score: 20
Accepted
time: 216ms
memory: 380248kb
Test #18:
score: 20
Accepted
time: 134ms
memory: 382680kb
Test #19:
score: 20
Accepted
time: 174ms
memory: 383724kb
Test #20:
score: 20
Accepted
time: 175ms
memory: 382532kb
Subtask #5:
score: 10
Accepted
Test #21:
score: 10
Accepted
time: 4426ms
memory: 597364kb
Test #22:
score: 10
Accepted
time: 4125ms
memory: 599284kb
Test #23:
score: 10
Accepted
time: 4080ms
memory: 606828kb
Test #24:
score: 10
Accepted
time: 4044ms
memory: 600884kb
Test #25:
score: 10
Accepted
time: 4079ms
memory: 598860kb
Subtask #6:
score: 10
Accepted
Test #26:
score: 10
Accepted
time: 994ms
memory: 458508kb
Test #27:
score: 10
Accepted
time: 977ms
memory: 456420kb
Test #28:
score: 10
Accepted
time: 981ms
memory: 456744kb
Test #29:
score: 10
Accepted
time: 990ms
memory: 454260kb
Test #30:
score: 10
Accepted
time: 977ms
memory: 452168kb
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: 3459ms
memory: 478484kb
Test #32:
score: 30
Accepted
time: 2267ms
memory: 470644kb
Test #33:
score: 30
Accepted
time: 1576ms
memory: 464576kb
Test #34:
score: 30
Accepted
time: 1621ms
memory: 469252kb
Test #35:
score: 30
Accepted
time: 2117ms
memory: 468768kb
Test #36:
score: 30
Accepted
time: 3461ms
memory: 472600kb
Test #37:
score: 30
Accepted
time: 2234ms
memory: 470444kb
Test #38:
score: 30
Accepted
time: 1577ms
memory: 464668kb
Test #39:
score: 30
Accepted
time: 1641ms
memory: 469316kb
Test #40:
score: 30
Accepted
time: 2169ms
memory: 472660kb