QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#505049#4408. 燃烧的呐球gxy001100 ✓2533ms357724kbC++236.0kb2024-08-04 18:46:332024-08-04 18:46:34

Judging History

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

  • [2024-08-04 18:46:34]
  • 评测
  • 测评结果:100
  • 用时:2533ms
  • 内存:357724kb
  • [2024-08-04 18:46:33]
  • 提交

answer

#include<iostream>
#include<vector>
#include<algorithm>
#define BUFSIZE 10000000
struct read{
	char buf[BUFSIZE],*p1,*p2,c;
	read():p1(buf),p2(buf){}
	char gc(void){
	    return p1==p2?(std::cin.read(p1=buf,BUFSIZE),p2=p1+std::cin.gcount(),p1==p2?EOF:*p1++):*p1++;
	}
	read& operator >>(int& x){
		c=gc(),x=0;
		for(;c<'0'||c>'9';c=gc());
		for(;c>='0'&&c<='9';c=gc())x=x*10+(c-'0');
		return *this;
	}
}cin;
using std::cout;
std::vector<int> v[1000010],x,y;
std::vector<std::pair<int,int>> t[1000010],h[1000010];
std::vector<std::pair<int,int>>*g;
int n,m,a[100010],b[100010],sz[1000010],xl[1000010],xr[1000010],yl[1000010],yr[1000010];
int f[100010],pcnt,col[100010],cs,*L,*R;
int find(int x){
	while(x!=f[x]) x=f[x]=f[f[x]];
	return x;
}
int rk[1000010];
int p[2000010],cct;
void dfs(int x){
	static int cnt=0;
	rk[x]=++cnt,sz[x]=1,p[++cct]=x;
	for(auto u:v[x]) dfs(u),sz[x]+=sz[u];
	p[++cct]=-x;
}
int const inf=1e9;
struct pnt{
	int mn,mnt;
	pnt():mn(inf),mnt(){}
	pnt(int x,int y):mn(x),mnt(y){}
	friend bool operator <(pnt const &a,pnt const &b){
		return a.mn<b.mn;
	}
	pnt operator -(int x)const{
		return pnt(mn-x,mnt);
	}
	pnt operator +(int x)const{
		return pnt(mn+x,mnt);
	}
}res[100010];
struct node{
	pnt m,xm;
	node():m(),xm(){}
	node(pnt const &x):m(x),xm(){}
	node(int x,int y):m(x,y),xm(){}
	node(pnt const &x,pnt const &y):m(x),xm(y){}
	void operator +=(node const &y){
		if(y.m<m) xm=std::min(y.xm,col[m.mnt]==col[y.m.mnt]?xm:m),m=y.m;
		else xm=std::min(xm,col[y.m.mnt]==col[m.mnt]?y.xm:y.m);
	} 
	pnt query(int x)const{
		if(col[m.mnt]==col[x]) return xm;
		else return m;
	}
};
namespace sub1{
	node f[1000010],r[1000010];
	void work(){
		f[1]=node();
		for(int i=1;i<=cct;i++){
			int x=p[i];
			if(x<0){
				x=-x;
				for(auto u:v[x]) r[x]+=r[u];
				for(auto [i,u]:g[x]) res[i]=std::min(res[i],std::min(r[x].query(i)+sz[x]+sz[u],f[x].query(i)-sz[x]+sz[u]));
			}else{
				r[x]=node();
				for(auto [i,u]:g[x]) f[x]+=node(sz[x]+sz[u],i),r[x]+=node(-sz[x]+sz[u],i);
				for(auto u:v[x]) f[u]=f[x];
			}
		}
	}
}
node tr[1800010];
namespace sub2{
	int cnt,ls[1800010],rs[1800010],rt[1000010];
	void update(int p,node const &v,int &x,int l=1,int r=cs){
		if(!x) x=++cnt,ls[x]=rs[x]=0;
		tr[x]+=v;
		if(l==r) return;
		int mid=(l+r)>>1;
		if(p<=mid) update(p,v,ls[x],l,mid);
		else update(p,v,rs[x],mid+1,r);
	}
	void merge(int &x,int y){
		if(!x||!y) return x|=y,void();
		tr[x]+=tr[y];
		merge(ls[x],ls[y]),merge(rs[x],rs[y]);
	}
	pnt query(int pl,int pr,int i,int x,int l=1,int r=cs){
		if(l==pl&&r==pr) return tr[x].query(i);
		int mid=(l+r)>>1;
		if(pr<=mid) return query(pl,pr,i,ls[x],l,mid);
		else if(pl>mid) return query(pl,pr,i,rs[x],mid+1,r);
		else return std::min(query(pl,mid,i,ls[x],l,mid),query(mid+1,pr,i,rs[x],mid+1,r));
	}
	void work(){
		for(int i=1;i<=cct;i++){
			int x=p[i];
			if(x<0){
				x=-x;
				rt[x]=0;	
				for(auto u:v[x]) merge(rt[x],rt[u]);
				for(auto [i,u]:g[x]) update(L[u],node(-sz[x]-sz[u],i),rt[x]);
				for(auto [i,u]:g[x]) res[i]=std::min(res[i],query(L[u],R[u],i,rt[x])+sz[x]+sz[u]);
			}
		}
		for(int i=1;i<=cnt;i++) tr[i]=node();
		cnt=0;
	}
}
int M;
int tp,s[3600010],top[1000010];
node val[3600010];
namespace sub3{
	void update(int p,node const &v){
		for(p+=M;p;p>>=1) ++tp,s[tp]=p,val[tp]=tr[p],tr[p]+=v;
	}
	pnt query(int x,int y,int i){
		pnt ans;
		for(x+=M-1,y+=M+1;x^y^1;x>>=1,y>>=1){
			if(~x&1) ans=std::min(ans,tr[x^1].query(i));
			if(y&1) ans=std::min(ans,tr[y^1].query(i));
		}
		return ans;
	}
	void work(){
		M=1;
		while(M<cs) M<<=1;
		for(int i=1;i<=cct;i++){
			int x=p[i];
			if(x<0){
				x=-x;
				while(tp!=top[x]) tr[s[tp]]=val[tp],--tp;
			}else{
				top[x]=tp;
				for(auto [i,u]:g[x]) update(L[u],node(sz[x]-sz[u],i));
				for(auto [i,u]:g[x]) res[i]=std::min(res[i],query(L[u],R[u],i)-sz[x]+sz[u]);
			}
		}
	}
}
namespace sub4{
	void update(int x,int y,node const &v){
		for(x+=M-1,y+=M+1;x^y^1;x>>=1,y>>=1){
			if(~x&1) ++tp,s[tp]=x^1,val[tp]=tr[x^1],tr[x^1]+=v;
			if(y&1) ++tp,s[tp]=y^1,val[tp]=tr[y^1],tr[y^1]+=v;
		}
	}
	pnt query(int p,int i){
		pnt ans;
		for(p+=M;p;p>>=1) ans=std::min(ans,tr[p].query(i));
		return ans;
	}
	void work(){
		M=1;
		while(M<cs) M<<=1;
		for(int i=1;i<=cct;i++){
			int x=p[i];
			if(x<0){
				x=-x;
				while(tp!=top[x]) tr[s[tp]]=val[tp],--tp;
			}else{
				top[x]=tp;
				for(auto [i,u]:g[x]) update(L[u],R[u],node(sz[x]+sz[u],i));
				for(auto [i,u]:g[x]) res[i]=std::min(res[i],query(L[u],i)-sz[x]-sz[u]);
			}
		}
	}
}
int main(){
	std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
	cin>>n>>m;
	for(int i=1,x;i<n;i++) cin>>x,v[x].push_back(i+1);
	dfs(1);
	for(int i=1;i<=m;i++){
		cin>>a[i]>>b[i],t[a[i]].emplace_back(i,b[i]),h[b[i]].emplace_back(i,a[i]),f[i]=i;
		x.push_back(rk[b[i]]),y.push_back(rk[a[i]]);
	}
	std::sort(x.begin(),x.end());
	std::sort(y.begin(),y.end());
	x.resize(std::unique(x.begin(),x.end())-x.begin());
	y.resize(std::unique(y.begin(),y.end())-y.begin());
	for(int i=1;i<=m;i++)
		xl[b[i]]=std::lower_bound(x.begin(),x.end(),rk[b[i]])-x.begin()+1,xr[b[i]]=std::upper_bound(x.begin(),x.end(),rk[b[i]]+sz[b[i]]-1)-x.begin(),
		yl[a[i]]=std::lower_bound(y.begin(),y.end(),rk[a[i]])-y.begin()+1,yr[a[i]]=std::upper_bound(y.begin(),y.end(),rk[a[i]]+sz[a[i]]-1)-y.begin();
	pcnt=m;
	long long ans=0;
	while(pcnt>1){
		for(int i=1;i<=m;i++) col[i]=find(i);
		node tt;
		for(int i=1;i<=m;i++) tt+=node(sz[a[i]]+sz[b[i]],i);
		for(int i=1;i<=m;i++) res[i]=tt.query(i)+sz[a[i]]+sz[b[i]];
		g=t,cs=x.size(),L=xl,R=xr;
		sub1::work();
		sub2::work();
		sub3::work();
		sub4::work();
		g=h,cs=y.size(),L=yl,R=yr;
		sub1::work();
		sub3::work();
		static pnt link[100010];
		static int c[100010];
		for(int i=1;i<=m;i++) link[i]=pnt(),c[i]=0;
		for(int i=1;i<=m;i++) if(res[i]<link[col[i]]) link[col[i]]=res[i],c[col[i]]=i;
		for(int i=1;i<=m;i++) if(col[i]==i){
			int u=find(link[i].mnt),v=find(c[i]);
			if(u!=v) f[u]=v,ans+=link[i].mn,--pcnt;
		}
	}
	cout<<ans<<'\n';
	return 0;
}

詳細信息

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 8ms
memory: 149256kb

Test #2:

score: 10
Accepted
time: 12ms
memory: 149320kb

Test #3:

score: 10
Accepted
time: 4ms
memory: 149060kb

Test #4:

score: 10
Accepted
time: 16ms
memory: 154612kb

Test #5:

score: 10
Accepted
time: 15ms
memory: 156780kb

Subtask #2:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #6:

score: 10
Accepted
time: 1107ms
memory: 269392kb

Test #7:

score: 10
Accepted
time: 674ms
memory: 265092kb

Test #8:

score: 10
Accepted
time: 434ms
memory: 259200kb

Test #9:

score: 10
Accepted
time: 464ms
memory: 263228kb

Test #10:

score: 10
Accepted
time: 637ms
memory: 262540kb

Subtask #3:

score: 10
Accepted

Dependency #2:

100%
Accepted

Test #11:

score: 10
Accepted
time: 1698ms
memory: 276740kb

Test #12:

score: 10
Accepted
time: 1174ms
memory: 274864kb

Test #13:

score: 10
Accepted
time: 813ms
memory: 266560kb

Test #14:

score: 10
Accepted
time: 849ms
memory: 273672kb

Test #15:

score: 10
Accepted
time: 1097ms
memory: 271992kb

Subtask #4:

score: 20
Accepted

Test #16:

score: 20
Accepted
time: 126ms
memory: 154188kb

Test #17:

score: 20
Accepted
time: 148ms
memory: 160076kb

Test #18:

score: 20
Accepted
time: 113ms
memory: 156216kb

Test #19:

score: 20
Accepted
time: 125ms
memory: 159820kb

Test #20:

score: 20
Accepted
time: 156ms
memory: 150292kb

Subtask #5:

score: 10
Accepted

Test #21:

score: 10
Accepted
time: 2487ms
memory: 357720kb

Test #22:

score: 10
Accepted
time: 2481ms
memory: 357724kb

Test #23:

score: 10
Accepted
time: 2490ms
memory: 357144kb

Test #24:

score: 10
Accepted
time: 2533ms
memory: 355556kb

Test #25:

score: 10
Accepted
time: 2481ms
memory: 355024kb

Subtask #6:

score: 10
Accepted

Test #26:

score: 10
Accepted
time: 687ms
memory: 238804kb

Test #27:

score: 10
Accepted
time: 684ms
memory: 241864kb

Test #28:

score: 10
Accepted
time: 698ms
memory: 242260kb

Test #29:

score: 10
Accepted
time: 691ms
memory: 240620kb

Test #30:

score: 10
Accepted
time: 684ms
memory: 240684kb

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: 2320ms
memory: 283444kb

Test #32:

score: 30
Accepted
time: 1520ms
memory: 282484kb

Test #33:

score: 30
Accepted
time: 1123ms
memory: 276100kb

Test #34:

score: 30
Accepted
time: 1197ms
memory: 281020kb

Test #35:

score: 30
Accepted
time: 1462ms
memory: 280232kb

Test #36:

score: 30
Accepted
time: 2332ms
memory: 284140kb

Test #37:

score: 30
Accepted
time: 1495ms
memory: 282172kb

Test #38:

score: 30
Accepted
time: 1133ms
memory: 276140kb

Test #39:

score: 30
Accepted
time: 1144ms
memory: 280804kb

Test #40:

score: 30
Accepted
time: 1448ms
memory: 280048kb