QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#93596#4408. 燃烧的呐球chenshi#100 ✓8926ms301936kbC++5.1kb2023-04-01 19:51:222023-04-01 19:51:23

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-01 19:51:23]
  • 评测
  • 测评结果:100
  • 用时:8926ms
  • 内存:301936kb
  • [2023-04-01 19:51:22]
  • 提交

answer

#include<cstdio>
#include<utility>
#include<vector>
#include<iostream>
using namespace std;
const int o=1e6+10,O=4e6+10;
int n,m,p[o],X[o],Y[o],dfn[o],ed[o],tot,nfd[o*2],h[o],cnt,fa[o],s[o],tp,Tp[o],ptn[o],w[o],col[o];
int rt[o],ls[O],rs[O];long long ans;vector<int> vec[o];
int fr(int x){return fa[x]==x?x:fa[x]=fr(fa[x]);}
struct Edge{int v,p;}e[o];
inline void ad(int U,int V){e[++cnt].v=V;e[cnt].p=h[U];h[U]=cnt;}
struct info{
	pair<int,int> fi,se;
	info(int a=O,int b=0,int c=O,int d=0):fi(make_pair(a,b)),se(make_pair(c,d)){}
	inline void upd(info b){
		if(fi.first>b.fi.first) swap(fi,b.fi);
		if(b.fi.first<=se.first&&col[b.fi.second]-col[fi.second]) se=b.fi;
		if(b.se.first<=se.first&&col[b.se.second]-col[fi.second]) se=b.se;
	}
}tmp,mn[O],Val[O],*st[O];
void dfs(int nw){
	dfn[nw]=++tot;s[nfd[++cnt]=nw]=1;
	for(int i=h[nw];i;i=e[i].p) dfs(e[i].v),s[nw]+=s[e[i].v];
	ed[nw]=tot;nfd[++cnt]=-nw;
}
inline void upd(int x,const info&y,int d){
	x=col[x];
	if(y.fi.first+d<w[x]&&col[y.fi.second]-x) w[x]=y.fi.first+d,ptn[x]=y.fi.second;
	if(y.se.first+d<w[x]&&col[y.se.second]-x) w[x]=y.se.first+d,ptn[x]=y.se.second;
}
void modify1(int&id,int pos,const info&val,int l=1,int r=n){
	if(!id) mn[id=++cnt]=info(),ls[id]=rs[id]=0;
	st[++tp]=mn+id;Val[tp]=*st[tp];mn[id].upd(val);
	if(l==r) return;
	int md=l+r>>1;
	if(pos<=md) modify1(ls[id],pos,val,l,md);
	else modify1(rs[id],pos,val,md+1,r);
}
void query1(int id,int ql,int qr,int l=1,int r=n){
	if(!id) return;
	if(ql<=l&&r<=qr){tmp.upd(mn[id]);return;}
	int md=l+r>>1;
	if(ql<=md) query1(ls[id],ql,qr,l,md);
	if(md<qr) query1(rs[id],ql,qr,md+1,r);
}
void modify2(int&id,int ql,int qr,const info&val,int l=1,int r=n){
	if(!id) mn[id=++cnt]=info(),ls[id]=rs[id]=0;
	if(ql<=l&&r<=qr){st[++tp]=mn+id;Val[tp]=*st[tp];mn[id].upd(val);return;}
	int md=l+r>>1;
	if(ql<=md) modify2(ls[id],ql,qr,val,l,md);
	if(md<qr) modify2(rs[id],ql,qr,val,md+1,r);
}
void query2(int id,int pos,int l=1,int r=n){
	if(!id) return;
	tmp.upd(mn[id]);
	if(l==r) return;
	int md=l+r>>1;
	if(pos<=md) query2(ls[id],pos,l,md);
	else query2(rs[id],pos,md+1,r);
}
int merge(int x,int y){
	if(!x||!y) return x|y;
	mn[x].upd(mn[y]);
	ls[x]=merge(ls[x],ls[y]);rs[x]=merge(rs[x],rs[y]);
	return x;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=2;i<=n;++i) scanf("%d",&p[i]),ad(p[i],i);
	for(int i=1;i<=m;++i) scanf("%d%d",&X[i],&Y[i]),vec[X[i]].push_back(i),fa[i]=i;
	cnt=0;dfs(1);
	for(int num=m;num>1;){
		for(int i=1;i<=m;++i) ptn[i]=0,w[i]=O,col[i]=fr(i);
		//case1:sxi+syi+sxj+syj
		tmp=info();
		for(int i=1;i<=m;++i) tmp.upd(info(s[X[i]]+s[Y[i]],i));
		for(int i=1;i<=m;++i) upd(i,tmp,s[X[i]]+s[Y[i]]);
		//case2:sxi+syi+sxj-syj
		rt[0]=cnt=tp=0;
		for(int i=1;i<=m;++i) modify1(rt[0],dfn[Y[i]],info(s[X[i]]-s[Y[i]],i));
		for(int i=1;i<=m;++i) tmp=info(),query1(rt[0],dfn[Y[i]],ed[Y[i]]),upd(i,tmp,s[X[i]]+s[Y[i]]);
		//case3:sxi-syi+sxj+syj
		rt[0]=cnt=tp=0;
		for(int i=1;i<=m;++i) modify2(rt[0],dfn[Y[i]],ed[Y[i]],info(s[X[i]]+s[Y[i]],i));
		for(int i=1;i<=m;++i) tmp=info(),query2(rt[0],dfn[Y[i]]),upd(i,tmp,s[X[i]]-s[Y[i]]);
		//case4:sxi+syi-sxj+syj
		for(int i=1;i<=n;++i) mn[i]=info();
		for(int i=1;i<=m;++i) mn[X[i]].upd(info(-s[X[i]]+s[Y[i]],i));
		for(int i=n;i>1;--i) mn[p[i]].upd(mn[i]);
		for(int i=1;i<=m;++i) upd(i,mn[X[i]],s[X[i]]+s[Y[i]]);
		//case5:-sxi+syi+sxj+syj
		for(int i=1;i<=n;++i) mn[i]=info();
		for(int i=1;i<=m;++i) mn[X[i]].upd(info(s[X[i]]+s[Y[i]],i));
		for(int i=2;i<=n;++i) mn[i].upd(mn[p[i]]);
		for(int i=1;i<=m;++i) upd(i,mn[X[i]],-s[X[i]]+s[Y[i]]);
		//case6:sxi+syi-sxj-syj
		cnt=tp=0;
		for(int i=1;i<=n;++i) rt[i]=0;
		for(int i=1;i<=m;++i) modify1(rt[X[i]],dfn[Y[i]],info(-s[X[i]]-s[Y[i]],i));
		for(int i=n;i;--i){
			for(int j=vec[i].size(),t;j--;)
				t=vec[i][j],tmp=info(),query1(rt[i],dfn[Y[t]],ed[Y[t]]),upd(t,tmp,s[X[t]]+s[Y[t]]);
			if(i>1) rt[p[i]]=merge(rt[p[i]],rt[i]);
		}
		//case7:sxi-syi-sxj+syj
		cnt=tp=0;
		for(int i=1;i<=n;++i) rt[i]=0;
		for(int i=1;i<=m;++i) modify2(rt[X[i]],dfn[Y[i]],ed[Y[i]],info(-s[X[i]]+s[Y[i]],i));
		for(int i=n;i;--i){
			for(int j=vec[i].size(),t;j--;)
				t=vec[i][j],tmp=info(),query2(rt[i],dfn[Y[t]]),upd(t,tmp,s[X[t]]-s[Y[t]]);
			if(i>1) rt[p[i]]=merge(rt[p[i]],rt[i]);
		}
		//case8:-sxi+syi+sxj-syj
		rt[0]=cnt=tp=0;
		for(int i=1,u;i<=n*2;++i)
			if(nfd[i]<0) for(;tp>Tp[-nfd[i]];--tp) *st[tp]=Val[tp];
			else{
				Tp[u=nfd[i]]=tp;
				for(int j=vec[u].size(),t;j--;) t=vec[u][j],modify1(rt[0],dfn[Y[t]],info(s[X[t]]-s[Y[t]],t));
				for(int j=vec[u].size(),t;j--;)
					t=vec[u][j],tmp=info(),query1(rt[0],dfn[Y[t]],ed[Y[t]]),upd(t,tmp,-s[X[t]]+s[Y[t]]);
			}
		//case9:-sxi-syi+sxj+syj
		rt[0]=cnt=tp=0;
		for(int i=1,u;i<=n*2;++i)
			if(nfd[i]<0) for(;tp>Tp[-nfd[i]];--tp) *st[tp]=Val[tp];
			else{
				Tp[u=nfd[i]]=tp;
				for(int j=vec[u].size(),t;j--;) t=vec[u][j],modify2(rt[0],dfn[Y[t]],ed[Y[t]],info(s[X[t]]+s[Y[t]],t));
				for(int j=vec[u].size(),t;j--;)
					t=vec[u][j],tmp=info(),query2(rt[0],dfn[Y[t]]),upd(t,tmp,-s[X[t]]-s[Y[t]]);
			}
		//boruvka
		for(int i=1;i<=m;++i) if(fa[i]==i&&i-fr(ptn[i])) ans+=w[i],fa[fr(i)]=fr(ptn[i]),--num;
	}
	printf("%lld",ans);
	return 0;
}

详细

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 39ms
memory: 154212kb

Test #2:

score: 0
Accepted
time: 27ms
memory: 153644kb

Test #3:

score: 0
Accepted
time: 20ms
memory: 154284kb

Test #4:

score: 0
Accepted
time: 26ms
memory: 152712kb

Test #5:

score: 0
Accepted
time: 49ms
memory: 153856kb

Subtask #2:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #6:

score: 10
Accepted
time: 1304ms
memory: 205420kb

Test #7:

score: 0
Accepted
time: 900ms
memory: 202960kb

Test #8:

score: 0
Accepted
time: 688ms
memory: 202804kb

Test #9:

score: 0
Accepted
time: 670ms
memory: 203028kb

Test #10:

score: 0
Accepted
time: 899ms
memory: 202844kb

Subtask #3:

score: 10
Accepted

Dependency #2:

100%
Accepted

Test #11:

score: 10
Accepted
time: 3009ms
memory: 215668kb

Test #12:

score: 0
Accepted
time: 2053ms
memory: 215036kb

Test #13:

score: 0
Accepted
time: 1673ms
memory: 214316kb

Test #14:

score: 0
Accepted
time: 1550ms
memory: 214520kb

Test #15:

score: 0
Accepted
time: 1937ms
memory: 214888kb

Subtask #4:

score: 20
Accepted

Test #16:

score: 20
Accepted
time: 451ms
memory: 164956kb

Test #17:

score: 0
Accepted
time: 550ms
memory: 165516kb

Test #18:

score: 0
Accepted
time: 357ms
memory: 164400kb

Test #19:

score: 0
Accepted
time: 456ms
memory: 165680kb

Test #20:

score: 0
Accepted
time: 451ms
memory: 164276kb

Subtask #5:

score: 10
Accepted

Test #21:

score: 10
Accepted
time: 8821ms
memory: 301780kb

Test #22:

score: 0
Accepted
time: 8882ms
memory: 301936kb

Test #23:

score: 0
Accepted
time: 8921ms
memory: 301932kb

Test #24:

score: 0
Accepted
time: 8926ms
memory: 301772kb

Test #25:

score: 0
Accepted
time: 8588ms
memory: 301728kb

Subtask #6:

score: 10
Accepted

Test #26:

score: 10
Accepted
time: 2462ms
memory: 229140kb

Test #27:

score: 0
Accepted
time: 2529ms
memory: 229140kb

Test #28:

score: 0
Accepted
time: 2533ms
memory: 229068kb

Test #29:

score: 0
Accepted
time: 2504ms
memory: 229232kb

Test #30:

score: 0
Accepted
time: 2532ms
memory: 229136kb

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: 6036ms
memory: 236040kb

Test #32:

score: 0
Accepted
time: 3684ms
memory: 235032kb

Test #33:

score: 0
Accepted
time: 2983ms
memory: 233708kb

Test #34:

score: 0
Accepted
time: 3106ms
memory: 233908kb

Test #35:

score: 0
Accepted
time: 3774ms
memory: 234228kb

Test #36:

score: 0
Accepted
time: 6238ms
memory: 236144kb

Test #37:

score: 0
Accepted
time: 4152ms
memory: 234892kb

Test #38:

score: 0
Accepted
time: 3250ms
memory: 233680kb

Test #39:

score: 0
Accepted
time: 3129ms
memory: 233972kb

Test #40:

score: 0
Accepted
time: 3877ms
memory: 234288kb