QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#356321#8235. Top ClusterUSTC_fish_touching_team#WA 8ms114916kbC++142.8kb2024-03-17 17:32:212024-03-17 17:32:21

Judging History

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

  • [2024-03-17 17:32:21]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:114916kb
  • [2024-03-17 17:32:21]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
const long long inf=1e15+1;
#define ll long long
vector<ll >d[N],id[N];
int sz[N];
int w[N];
int ton[N];
int mexall=0;
int vis[N];
int ans[N];
long long dep[N];
vector<int >p[N],vp[N];
int rt,siz,zqdx;
int wclsh;
void grt(int x,int fa){
	sz[x]=1;
	int szn=0;
	for(int y:p[x])if(!vis[y]&&y!=fa){
		grt(y,x);
		sz[x]+=sz[y];
		szn=max(szn,sz[y]);
	}
	szn=max(szn,zqdx-sz[x]);
	if(siz>szn)siz=szn,rt=x;
}
void gx(int &x,int y){
	x=min(x,y);
}
int t[N];
void add(int x,int y){
	x=wclsh-x+1;
	for(;x<=wclsh;x+=x&-x)t[x]=min(t[x],y);
}
int qr(int x){
	x=wclsh-x+1;
	int ans=1e9;
	for(;x;x-=x&-x)ans=min(t[x],ans);
	return ans;
}
ll cp[N],lsh[N];
void dfs(int x,int fa){
	for(int i=0;i<p[x].size();i++)if(p[x][i]!=fa&&!vis[p[x][i]]){
		int y=p[x][i];
		dfs(y,x);
	}
	for(int i=0;i<d[x].size();i++){
		gx(ans[id[x][i]],qr(cp[id[x][i]]));
	}
}
void adfs(int x,int fa){
	sz[x]=1;
	for(int y:p[x])if(y!=fa&&!vis[y]){
		adfs(y,x);sz[x]+=sz[y];
	}
	add(dep[x],w[x]);
}
void aadfs(int x,int fa){
	for(int i=0;i<p[x].size();i++)if(p[x][i]!=fa&&!vis[p[x][i]]){
		int y=p[x][i];
		dep[y]=dep[x]+vp[x][i];
		lsh[++lsh[0]]=dep[y];
		aadfs(y,x);
	}
	for(int i=0;i<d[x].size();i++){
		cp[id[x][i]]=d[x][i]-dep[x]+1;
		lsh[++lsh[0]]=cp[id[x][i]];
	}
}
void aaadfs(int x,int fa){
	for(int i=0;i<p[x].size();i++)if(p[x][i]!=fa&&!vis[p[x][i]]){
		int y=p[x][i];
		dep[y]=lower_bound(lsh+1,lsh+1+wclsh,dep[y])-lsh;
		aaadfs(y,x);
	}
	for(int i=0;i<d[x].size();i++){
		cp[id[x][i]]=lower_bound(lsh+1,lsh+1+wclsh,cp[id[x][i]])-lsh;
	}
}
void sol(int x,int dx){
	if(vis[x])return ;
	if(dx==1)return;
	rt=0;
	siz=1e9;
	zqdx=dx;
	grt(x,0);
	x=rt;
	
	aadfs(x,0); 
	sort(lsh+1,lsh+1+lsh[0]);
	wclsh=unique(lsh+1,lsh+1+lsh[0])-lsh-1;
	
	dep[x]=lower_bound(lsh+1,lsh+1+wclsh,dep[x])-lsh;
	aaadfs(x,0);
	
	for(int i=0;i<=wclsh;i++)t[i]=1e9;
	
	add(dep[x],w[x]);
	for(int i=0;i<p[x].size();i++)dfs(p[x][i],x),adfs(p[x][i],x);
	
	for(int i=0;i<=wclsh;i++)t[i]=1e9;
	
	add(dep[x],w[x]);
	for(int i=(int)p[x].size()-1;i>=0;i--)dfs(p[x][i],x),adfs(p[x][i],x);
	
	for(int i=0;i<d[x].size();i++){
		gx(ans[id[x][i]],qr(cp[id[x][i]]));
	}
	
	for(int i=0;i<=wclsh;i++)t[i]=1e9;
	vis[x]=1;
	for(int y:p[x])sol(y,sz[y]);

}
int main(){
	int n,q;
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		scanf("%d",&w[i]);
		if(w[i]<=n)ton[w[i]]=1;
		else w[i]=n+1;
	}
	while(ton[mexall])mexall++;
	for(int i=1;i<n;i++){
		int v,u,l;
		scanf("%d%d%d",&u,&v,&l);
		p[u].push_back(v);
		vp[u].push_back(l);
		p[v].push_back(u);
		vp[v].push_back(l);
	}
	for(int i=1;i<=q;i++){
		int x,k;
		scanf("%d%d",&x,&k);
		id[x].push_back(i);
		d[x].push_back(k);
	}
	memset(ans,63,sizeof(ans));
	sol(1,n);
	for(int i=1;i<=q;i++){
		printf("%d\n",min(mexall,ans[i]));
	}
	
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 8ms
memory: 114916kb

input:

5 4
3 9 0 1 2
1 2 10
3 1 4
3 4 3
3 5 2
3 0
1 0
4 6
4 7

output:

0
0
3
4

result:

wrong answer 1st numbers differ - expected: '1', found: '0'