QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#351865#7211. AttackNaganohara_YoimiyaWA 4ms10916kbC++144.5kb2024-03-12 16:42:552024-03-12 16:42:55

Judging History

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

  • [2024-03-12 16:42:55]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:10916kb
  • [2024-03-12 16:42:55]
  • 提交

answer

#include<bits/stdc++.h>

#define ll long long
#define mk make_pair
#define fi first
#define se second

using namespace std;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
	for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
	return x*f;
}

template<typename T>void cmax(T &x,T v){x=max(x,v);}
template<typename T>void cmin(T &x,T v){x=min(x,v);}

const int N=3e5+5;
int n,q,a[N],dfn[N],sz[N];
vector<int>G[N];
struct BIT{
	int c[N];
	int lowbit(int x){return x&(-x);}
	void add(int x,int v){for(int i=x;i<=n;i+=lowbit(i))c[i]+=v;}
	int qsum(int x){
		if(x==0)return 0;int res=0;
		for(int i=x;i;i-=lowbit(i))res+=c[i];
		return res;
	}
}T1;

struct sgt{
	int sum[N<<2],lz[N<<2],d[N<<2];
	// tag == 0 : do nothing
	// tag == 1 : cov -> 0
	// tag == 2 : cov -> initial value
	#define ls(p) (p<<1)
	#define rs(p) (p<<1|1)
	void pushup(int p){d[p]=d[ls(p)]+d[rs(p)];}
	void build(int l,int r,int p){
		lz[p]=0;
		if(l==r)return d[p]=sum[p]=a[l],void();
		int mid=(l+r)>>1;build(l,mid,ls(p)),build(mid+1,r,rs(p)),sum[p]=sum[ls(p)]+sum[rs(p)],pushup(p);
	}
	void app(int f,int p){
		if(f==1)d[p]=0;
		if(f==2)d[p]=sum[p];
		if(f!=0)lz[p]=f;
	}
	void pushdown(int p){if(lz[p])app(lz[p],ls(p)),app(lz[p],rs(p)),lz[p]=0;}
	void mul(int l,int r,int f,int ql,int qr,int p){
		if(l<=ql&&qr<=r)return app(f,p);
		int mid=(ql+qr)>>1;pushdown(p);
		if(l<=mid)mul(l,r,f,ql,mid,ls(p));
		if(r>mid)mul(l,r,f,mid+1,qr,rs(p));
		pushup(p);
	}
	int qsum(int l,int r,int ql,int qr,int p){
		if(l>r)return 0;
		if(l<=ql&&qr<=r)return d[p];
		int mid=(ql+qr)>>1,ans=0;pushdown(p);
		if(l<=mid)ans+=qsum(l,r,ql,mid,ls(p));
		if(r>mid)ans+=qsum(l,r,mid+1,qr,rs(p));
		return ans;
	}
	int getpos(int lim,int ql,int qr,int p){ // min k s.t. sum ql...k >= lim
//		cout<<"getpos lim = "<<lim<<" [ql,qr] = ["<<ql<<","<<qr<<"] p = "<<p<<" d = "<<d[p]<<endl;
		if(d[p]<lim)return -1;
		if(ql==qr)return ql;
		int mid=(ql+qr)>>1;pushdown(p);
		if(d[ls(p)]>=lim)return getpos(lim,ql,mid,ls(p));
		else return getpos(lim-d[ls(p)],mid+1,qr,rs(p));
	}
}T2;

int hson[N],top[N],fa[N],dep[N],idfn[N];
void dfs1(int u){
	sz[u]=1,dep[u]=dep[fa[u]]+1;
	for(int v:G[u])if(v!=fa[u]){
		fa[v]=u,dfs1(v),sz[u]+=sz[v];
		if(sz[v]>sz[hson[u]])hson[u]=v;
	}
}
int dfc=0;
void dfs2(int u,int tp){
	top[u]=tp,idfn[dfn[u]=++dfc]=u;
	if(hson[u])dfs2(hson[u],tp);
	for(int v:G[u])if(v!=fa[u]&&v!=hson[u])dfs2(v,v);
}

int qval(int x){return T1.qsum(dfn[x]+sz[x]-1)-T1.qsum(dfn[x]-1);}
void prework(){
	dfs1(1),dfs2(1,1);
	for(int i=1;i<=n;i++)T1.add(dfn[i],a[i]);
	T2.build(1,n,1);
//	cout<<"DFN : ";for(int i=1;i<=n;i++)cout<<idfn[i]<<" ";puts("");
}

void solve(vector<int>nodes){
	nodes.emplace_back(1);
	sort(nodes.begin(),nodes.end(),[&](int x,int y){return dfn[x]>dfn[y];});
	
//	cout<<"solve nodes = ";for(int x:nodes)cout<<x<<" ";puts("");
	vector<int>ans;
	auto calc=[&](int u){
		int L=dfn[u],R=dfn[u]+sz[u]-1,sum=T2.qsum(L,R,1,n,1),lim=(int)(sum/2)+1;
		int s=T2.qsum(1,L-1,1,n,1)+lim;lim--;
		int p=T2.getpos(s,1,n,1);p=idfn[p];
//		cout<<"calc u = "<<u<<" -> p = "<<p<<endl;
		
		auto getans=[&](int l,int r){
			int ans=l;
//			cout<<"getans "<<l<<" "<<r<<" lim = "<<lim<<endl;
			while(l<=r){
				int mid=(l+r)>>1;
//				cout<<"mid = "<<mid<<" qval = "<<qval(idfn[mid])<<endl;
				if(qval(idfn[mid])>=lim)ans=mid,l=mid+1;
				else r=mid-1;
			}
			int u=idfn[ans],v=fa[u];
			if(sum%2==0&&qval(u)==sum/2)return min(u,v);
			return u;
		};
		while(top[p]!=top[u]){
			if(qval(top[p])<lim)p=fa[top[p]];
			else return getans(dfn[top[p]],dfn[p]);
		}
		return getans(dfn[u],dfn[p]);
	};
	
	vector<pair<int,int> >adds;
	for(int x:nodes){
		ans.emplace_back(calc(x));
		int cursum=qval(x);
		T1.add(dfn[x],-cursum),T2.mul(dfn[x],dfn[x]+sz[x]-1,1,1,n,1);
		adds.emplace_back(mk(dfn[x],cursum));
	}
	
	T2.mul(1,n,2,1,n,1);
	for(auto [x,y]:adds)T1.add(x,y);
	
	sort(ans.begin(),ans.end());
	for(int x:ans)cout<<x<<" ";puts("");
}

signed main(void){

#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
#endif

	n=read(),q=read();
	for(int i=1;i<=n;i++)a[i]=read();
	vector<pair<int,int> >edges(n);
	for(int i=1;i<=n-1;i++){
		int u=read(),v=read();edges[i]=mk(u,v);
		G[u].emplace_back(v),G[v].emplace_back(u);
	}
	prework();
//	puts("ok");
	for(int i=1;i<=q;i++){
		int k=read();vector<int>nodes(k);
		for(int j=0;j<k;j++){
			int p=read();auto [u,v]=edges[p];
			if(v==fa[u])swap(u,v); // -> u == fa[v]
			nodes[j]=v;
		}
		solve(nodes);
	}

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 4ms
memory: 10916kb

input:

5 2
1 1 1 1 1
1 2
1 3
2 4
2 5
1 1
4 1 2 3 4

output:

1 4 
1 2 3 4 5 

result:

wrong answer 2nd numbers differ - expected: '2', found: '4'