QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#887659 | #4408. 燃烧的呐球 | cqbztzl | 100 ✓ | 8437ms | 1176392kb | C++14 | 10.9kb | 2025-02-07 18:57:15 | 2025-02-07 18:57:16 |
Judging History
answer
#include<bits/stdc++.h>
#define pii pair<int,int>
#define mp(a,b) make_pair(a,b)
#define ull unsigned long long
using namespace std;
int n,m,tot,w[1000005],fa[100005],len[1000005],f[1000005],son[1000005],dfn[1000005],Dfn[1000005];
long long ans;
vector<int>g[1000005];
struct node{
int x,y;
}a[100005];
inline int find(int x){
if(fa[x]==x)return x;
else return fa[x]=find(fa[x]);
}
void dfs(int x,int fa){
w[x]=1;
len[x]=len[fa]+1;
dfn[x]=++tot;
Dfn[tot]=x;
for(int v:g[x]){
dfs(v,x);
w[x]+=w[v];
if(w[son[x]]<w[v])son[x]=v;
}
}
int res[100005],to[100005];
struct Val{
int minn,idm,oth,ido;
inline Val(){minn=oth=1e8,idm=ido=-1;}
inline Val(int minn,int idm,int oth=1e8,int ido=-1):minn(minn),idm(idm),oth(oth),ido(ido){}
};
int col[100005];
inline Val Merge(Val x,Val y){
if(x.idm==-1)return y;
if(y.idm==-1)return x;
Val z;
if(x.minn>y.minn)swap(x,y);
z.minn=x.minn;
z.idm=x.idm;
if(col[x.idm]!=col[y.idm]){
z.oth=min(x.oth,y.minn);
if(z.oth==x.oth)z.ido=x.ido;
else z.ido=y.idm;
}
else{
z.oth=min(x.oth,y.oth);
if(z.oth==x.oth)z.ido=x.ido;
else z.ido=y.ido;
}
// cerr<<x.minn<<" "<<x.idm<<' '<<x.oth<<' '<<x.ido<<" "<<y.minn<<" "<<y.idm<<' '<<y.oth<<' '<<y.ido<<" "<<z.minn<<" "<<z.idm<<' '<<z.oth<<' '<<z.ido<<endl;
return z;
}
struct ST{
int rt[1000005],cnt;
void clear(){
for(int i=1;i<=n;i++)rt[i]=0;
cnt=0;
c[0].minn=Val();
}
struct Node{
int son[2];
Val minn;
}c[10000005];
int New(){
cnt++;
c[cnt].son[0]=c[cnt].son[1]=0;
c[cnt].minn=Val();
return cnt;
}
void Add(int &q,int L,int R,int x,Val y){
if(!q)q=New();
if(L==R){
c[q].minn=Merge(c[q].minn,y);
return;
}
int mid=L+R>>1;
if(x<=mid)Add(c[q].son[0],L,mid,x,y);
else Add(c[q].son[1],mid+1,R,x,y);
c[q].minn=Merge(c[c[q].son[0]].minn,c[c[q].son[1]].minn);
}
Val Get(int q,int L,int R,int l,int r){
// cerr<<q<<" "<<L<<" "<<R<<' '<<l<<' '<<r<<endl;
if(!q)return Val();
if(l<=L&&R<=r)return c[q].minn;
int mid=L+R>>1;
if(r<=mid)return Get(c[q].son[0],L,mid,l,r);
if(mid<l)return Get(c[q].son[1],mid+1,R,l,r);
return Merge(Get(c[q].son[0],L,mid,l,r),Get(c[q].son[1],mid+1,R,l,r));
}
int Merget(int q1,int q2,int L,int R){
if(!q1||!q2)return q1+q2;
c[q1].minn=Merge(c[q1].minn,c[q2].minn);
if(L==R)return q1;
int mid=L+R>>1;
c[q1].son[0]=Merget(c[q1].son[0],c[q2].son[0],L,mid);
c[q1].son[1]=Merget(c[q1].son[1],c[q2].son[1],mid+1,R);
return q1;
}
void dfs(int q,int L,int R){
if(!q)return;
if(L==R){
cerr<<q<<' '<<L<<" "<<L<<' '<<c[q].minn.minn<<" "<<c[q].minn.idm<<' '<<c[q].minn.oth<<' '<<c[q].minn.ido<<endl;
return;
}
cerr<<q<<" "<<L<<' '<<R<<' '<<c[q].minn.minn<<" "<<c[q].minn.idm<<' '<<c[q].minn.oth<<' '<<c[q].minn.ido<<endl;
int mid=L+R>>1;
dfs(c[q].son[0],L,mid);
dfs(c[q].son[1],mid+1,R);
}
};
struct ST1{
int rt[1000005],cnt;
void clear(){
for(int i=1;i<=n;i++)rt[i]=0;
cnt=0;
c[0].minn=Val();
}
struct Node{
int son[2];
Val minn;
}c[10000005];
int New(int q){
cnt++;
c[cnt]=c[q];
return cnt;
}
void Add(int &q,int L,int R,int x,Val y){
q=New(q);
if(L==R){
c[q].minn=Merge(c[q].minn,y);
return;
}
int mid=L+R>>1;
if(x<=mid)Add(c[q].son[0],L,mid,x,y);
else Add(c[q].son[1],mid+1,R,x,y);
c[q].minn=Merge(c[c[q].son[0]].minn,c[c[q].son[1]].minn);
}
Val Get(int q,int L,int R,int l,int r){
if(!q)return Val();
if(l<=L&&R<=r)return c[q].minn;
int mid=L+R>>1;
if(r<=mid)return Get(c[q].son[0],L,mid,l,r);
if(mid<l)return Get(c[q].son[1],mid+1,R,l,r);
return Merge(Get(c[q].son[0],L,mid,l,r),Get(c[q].son[1],mid+1,R,l,r));
}
void dfs(int q,int L,int R){
if(!q)return;
if(L==R){
cerr<<q<<' '<<L<<' '<<c[q].minn.minn<<" "<<c[q].minn.idm<<' '<<c[q].minn.oth<<' '<<c[q].minn.ido<<endl;
return;
}
int mid=L+R>>1;
dfs(c[q].son[0],L,mid);
dfs(c[q].son[1],mid+1,R);
cerr<<q<<" "<<L<<' '<<R<<' '<<c[q].minn.minn<<" "<<c[q].minn.idm<<' '<<c[q].minn.oth<<' '<<c[q].minn.ido<<endl;
}
};
vector<int>posx[1000005],posy[1000005];
namespace S1{
Val x[1000005];
void dfs1(int u){
x[u]=Val();
for(int p:posy[u]){
x[u]=Merge(x[u],Val(w[a[p].x]-w[a[p].y],p));
}
for(int v:g[u]){
dfs1(v);
x[u]=Merge(x[u],x[v]);
}
for(int p:posy[u]){
int v,t;
if(col[p]==col[x[u].idm]){
v=w[a[p].x]+w[a[p].y]+x[u].oth;
t=x[u].ido;
}
else{
v=w[a[p].x]+w[a[p].y]+x[u].minn;
t=x[u].idm;
}
if(v<res[p]){
res[p]=v;
to[p]=t;
}
}
}
void dfs2(int u){
x[u]=Val();
for(int p:posx[u]){
x[u]=Merge(x[u],Val(-w[a[p].x]+w[a[p].y],p));
}
for(int v:g[u]){
dfs2(v);
x[u]=Merge(x[u],x[v]);
}
for(int p:posx[u]){
int v,t;
if(col[p]==col[x[u].idm]){
v=w[a[p].x]+w[a[p].y]+x[u].oth;
t=x[u].ido;
}
else{
v=w[a[p].x]+w[a[p].y]+x[u].minn;
t=x[u].idm;
}
if(v<res[p]){
res[p]=v;
to[p]=t;
}
}
}
void dfs3(int u,Val tag){
for(int p:posx[u]){
tag=Merge(tag,Val(w[a[p].x]+w[a[p].y],p));
}
for(int p:posx[u]){
int v,t;
if(col[p]==col[tag.idm]){
v=-w[a[p].x]+w[a[p].y]+tag.oth;
t=tag.ido;
}
else{
v=-w[a[p].x]+w[a[p].y]+tag.minn;
t=tag.idm;
}
if(v<res[p]){
res[p]=v;
to[p]=t;
}
}
for(int v:g[u]){
dfs3(v,tag);
}
}
void dfs4(int u,Val tag){
for(int p:posy[u]){
tag=Merge(tag,Val(w[a[p].x]+w[a[p].y],p));
}
for(int p:posy[u]){
int v,t;
if(col[p]==col[tag.idm]){
v=w[a[p].x]-w[a[p].y]+tag.oth;
t=tag.ido;
}
else{
v=w[a[p].x]-w[a[p].y]+tag.minn;
t=tag.idm;
}
if(v<res[p]){
res[p]=v;
to[p]=t;
}
}
for(int v:g[u]){
dfs4(v,tag);
}
}
void init(){
for(int i=1;i<=m;i++)x[i]=Val(w[a[i].x]+w[a[i].y],i);
Val minn;
for(int i=1;i<=m;i++)minn=Merge(minn,x[i]);
// cerr<<minn.minn<<' '<<minn.idm<<' '<<minn.oth<<' '<<minn.ido<<endl;
for(int i=1;i<=m;i++){
int v,t;
if(col[i]==col[minn.idm]){
v=w[a[i].x]+w[a[i].y]+minn.oth;
t=minn.ido;
}
else{
v=w[a[i].x]+w[a[i].y]+minn.minn;
t=minn.idm;
}
if(v<res[i]){
res[i]=v;
to[i]=t;
}
}
dfs1(1);
dfs2(1);
dfs3(1,Val());
dfs4(1,Val());
}
}
namespace S2{
ST T;
void dfs(int u){
for(int p:posx[u]){
// cerr<<u<<":"<<p<<endl;
T.Add(T.rt[u],1,n,dfn[a[p].y],Val(-w[a[p].x]-w[a[p].y],p));
}
for(int v:g[u]){
dfs(v);
T.rt[u]=T.Merget(T.rt[u],T.rt[v],1,n);
}
// cerr<<u<<"::"<<endl;
// T.dfs(T.rt[u],1,n);cerr<<endl;
for(int p:posx[u]){
int v,t;
Val minn=T.Get(T.rt[u],1,n,dfn[a[p].y],dfn[a[p].y]+w[a[p].y]-1);
// cerr<<p<<" "<<minn.minn<<" "<<minn.idm<<" "<<minn.oth<<" "<<minn.ido<<endl;
if(col[p]==col[minn.idm]){
v=w[a[p].x]+w[a[p].y]+minn.oth;
t=minn.ido;
}
else{
v=w[a[p].x]+w[a[p].y]+minn.minn;
t=minn.idm;
}
// cerr<<"="<<p<<' '<<v<<" "<<t<<endl;
if(v<res[p]){
res[p]=v;
to[p]=t;
}
}
}
void init(){
T.clear();
dfs(1);
}
}
namespace S3{
ST1 T;
void dfs1(int u){
for(int p:posx[u]){
T.Add(T.rt[u],1,n,dfn[a[p].y],Val(w[a[p].x]-w[a[p].y],p));
}
for(int p:posx[u]){
int v,t;
Val minn=T.Get(T.rt[u],1,n,dfn[a[p].y],dfn[a[p].y]+w[a[p].y]-1);
if(col[p]==col[minn.idm]){
v=-w[a[p].x]+w[a[p].y]+minn.oth;
t=minn.ido;
}
else{
v=-w[a[p].x]+w[a[p].y]+minn.minn;
t=minn.idm;
}
if(v<res[p]){
res[p]=v;
to[p]=t;
}
}
for(int v:g[u]){
T.rt[v]=T.rt[u];
dfs1(v);
}
}
void dfs2(int u){
for(int p:posy[u]){
T.Add(T.rt[u],1,n,dfn[a[p].x],Val(-w[a[p].x]+w[a[p].y],p));
}
for(int p:posy[u]){
int v,t;
Val minn=T.Get(T.rt[u],1,n,dfn[a[p].x],dfn[a[p].x]+w[a[p].x]-1);
if(col[p]==col[minn.idm]){
v=w[a[p].x]-w[a[p].y]+minn.oth;
t=minn.ido;
}
else{
v=w[a[p].x]-w[a[p].y]+minn.minn;
t=minn.idm;
}
if(v<res[p]){
res[p]=v;
to[p]=t;
}
}
for(int v:g[u]){
T.rt[v]=T.rt[u];
dfs2(v);
}
}
void init(){
T.clear();
dfs1(1);
T.clear();
dfs2(1);
}
}
struct ST2{
int rt[1000005],cnt;
void clear(){
for(int i=1;i<=n;i++)rt[i]=0;
cnt=0;
c[0].minn=Val();
}
struct Node{
int son[2];
Val minn;
}c[10000005];
inline int New(int q){
cnt++;
c[cnt]=c[q];
return cnt;
}
void Add(int &q,int L,int R,int l,int r,Val x){
q=New(q);
if(l<=L&&R<=r){
c[q].minn=Merge(c[q].minn,x);
return;
}
int mid=L+R>>1;
if(l<=mid)Add(c[q].son[0],L,mid,l,r,x);
if(mid<r)Add(c[q].son[1],mid+1,R,l,r,x);
}
Val Get(int q,int L,int R,int x){
if(!q)return Val();
if(L==R)return c[q].minn;
int mid=L+R>>1;
if(x<=mid)return Merge(c[q].minn,Get(c[q].son[0],L,mid,x));
else return Merge(c[q].minn,Get(c[q].son[1],mid+1,R,x));
}
void dfs(int q,int L,int R){
if(!q)return;
if(L==R){
cerr<<q<<' '<<L<<' '<<c[q].minn.minn<<" "<<c[q].minn.idm<<' '<<c[q].minn.oth<<' '<<c[q].minn.ido<<endl;
return;
}
int mid=L+R>>1;
dfs(c[q].son[0],L,mid);
dfs(c[q].son[1],mid+1,R);
cerr<<q<<" "<<L<<' '<<R<<' '<<c[q].minn.minn<<" "<<c[q].minn.idm<<' '<<c[q].minn.oth<<' '<<c[q].minn.ido<<endl;
}
};
namespace S4{
ST2 T;
void dfs(int u){
for(int p:posx[u]){
T.Add(T.rt[u],1,n,dfn[a[p].y],dfn[a[p].y]+w[a[p].y]-1,Val(w[a[p].x]+w[a[p].y],p));
}
for(int p:posx[u]){
int v,t;
Val minn=T.Get(T.rt[u],1,n,dfn[a[p].y]);
if(col[p]==col[minn.idm]){
v=-w[a[p].x]-w[a[p].y]+minn.oth;
t=minn.ido;
}
else{
v=-w[a[p].x]-w[a[p].y]+minn.minn;
t=minn.idm;
}
if(v<res[p]){
res[p]=v;
to[p]=t;
}
}
for(int v:g[u]){
T.rt[v]=T.rt[u];
dfs(v);
}
}
void init(){
T.clear();
dfs(1);
}
}
signed main()
{
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=2,x;i<=n;i++)scanf("%d",&x),g[x].push_back(i);
for(int i=1;i<=m;i++)scanf("%d%d",&a[i].x,&a[i].y),posx[a[i].x].push_back(i),posy[a[i].y].push_back(i);
for(int i=1;i<=m;i++)fa[i]=i;
dfs(1,0);
int k=m-1;
S1::init();
while(k){
for(int i=1;i<=m;i++){
res[i]=1e8,to[i]=-1;
}
for(int i=1;i<=m;i++)col[i]=find(i);
S1::init();
S2::init();
S3::init();
S4::init();
// cerr<<"AS"<<endl;
// cerr<<ans<<endl;
// for(int i=1;i<=m;i++)cerr<<find(i)<<' ';cerr<<endl;
// for(int i=1;i<=m;i++)cerr<<res[i]<<' ';cerr<<endl;
// for(int i=1;i<=m;i++)cerr<<to[i]<<' ';cerr<<endl;
for(int i=1;i<=m;i++){
int p=find(i);
if(i!=p){
if(res[i]<res[p]){
res[p]=res[i];
to[p]=to[i];
}
}
}
for(int i=1;i<=m;i++){
// cerr<<i<<' '<<fa[i]<<" "<<find(i)<<" "<<res[i]<<' '<<to[i]<<endl;
if(fa[i]==i){
if(find(i)!=find(to[i])){
k--;
ans+=res[i];
int v=find(to[i]);
fa[i]=v;
}
}
}
// cerr<<k<<endl;
}
printf("%lld",ans);
return 0;
}
Details
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 52ms
memory: 804744kb
Test #2:
score: 10
Accepted
time: 44ms
memory: 804752kb
Test #3:
score: 10
Accepted
time: 53ms
memory: 804880kb
Test #4:
score: 10
Accepted
time: 49ms
memory: 804876kb
Test #5:
score: 10
Accepted
time: 47ms
memory: 808844kb
Subtask #2:
score: 10
Accepted
Dependency #1:
100%
Accepted
Test #6:
score: 10
Accepted
time: 4428ms
memory: 848824kb
Test #7:
score: 10
Accepted
time: 2569ms
memory: 846292kb
Test #8:
score: 10
Accepted
time: 1251ms
memory: 840088kb
Test #9:
score: 10
Accepted
time: 1367ms
memory: 845060kb
Test #10:
score: 10
Accepted
time: 2008ms
memory: 843976kb
Subtask #3:
score: 10
Accepted
Dependency #2:
100%
Accepted
Test #11:
score: 10
Accepted
time: 5743ms
memory: 850696kb
Test #12:
score: 10
Accepted
time: 3753ms
memory: 848096kb
Test #13:
score: 10
Accepted
time: 1942ms
memory: 841772kb
Test #14:
score: 10
Accepted
time: 2217ms
memory: 846916kb
Test #15:
score: 10
Accepted
time: 3039ms
memory: 845908kb
Subtask #4:
score: 20
Accepted
Test #16:
score: 20
Accepted
time: 321ms
memory: 808056kb
Test #17:
score: 20
Accepted
time: 359ms
memory: 808060kb
Test #18:
score: 20
Accepted
time: 237ms
memory: 808060kb
Test #19:
score: 20
Accepted
time: 285ms
memory: 806144kb
Test #20:
score: 20
Accepted
time: 314ms
memory: 806136kb
Subtask #5:
score: 10
Accepted
Test #21:
score: 10
Accepted
time: 8001ms
memory: 1176156kb
Test #22:
score: 10
Accepted
time: 8102ms
memory: 1176392kb
Test #23:
score: 10
Accepted
time: 8437ms
memory: 1176392kb
Test #24:
score: 10
Accepted
time: 8339ms
memory: 1176260kb
Test #25:
score: 10
Accepted
time: 7887ms
memory: 1176148kb
Subtask #6:
score: 10
Accepted
Test #26:
score: 10
Accepted
time: 1183ms
memory: 832328kb
Test #27:
score: 10
Accepted
time: 1156ms
memory: 832168kb
Test #28:
score: 10
Accepted
time: 1160ms
memory: 832452kb
Test #29:
score: 10
Accepted
time: 1146ms
memory: 832216kb
Test #30:
score: 10
Accepted
time: 1242ms
memory: 832320kb
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: 6721ms
memory: 853736kb
Test #32:
score: 30
Accepted
time: 4324ms
memory: 851012kb
Test #33:
score: 30
Accepted
time: 2467ms
memory: 844648kb
Test #34:
score: 30
Accepted
time: 2665ms
memory: 849860kb
Test #35:
score: 30
Accepted
time: 3524ms
memory: 848688kb
Test #36:
score: 30
Accepted
time: 6804ms
memory: 853564kb
Test #37:
score: 30
Accepted
time: 4434ms
memory: 850948kb
Test #38:
score: 30
Accepted
time: 2513ms
memory: 844648kb
Test #39:
score: 30
Accepted
time: 2726ms
memory: 849860kb
Test #40:
score: 30
Accepted
time: 3725ms
memory: 848824kb