QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#351849#7211. AttackrageOfThunderWA 14ms10700kbC++144.3kb2024-03-12 16:26:062024-03-12 16:26:07

Judging History

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

  • [2024-03-12 16:26:07]
  • 评测
  • 测评结果:WA
  • 用时:14ms
  • 内存:10700kb
  • [2024-03-12 16:26:06]
  • 提交

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){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])-T1.qsum(dfn[x]);}
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;int lim=(int)(T2.qsum(L,R,1,n,1)/2)+1;
		int s=T2.qsum(1,L-1,1,n,1)+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;
			while(l<=r){
				int mid=(l+r)>>1;
				if(qval(idfn[mid])>=lim)ans=mid,l=mid+1;
				else r=mid-1;
			}
			return idfn[ans];
		};
		while(top[p]!=top[u]){
			int v=fa[top[p]];
			if(qval(v)<lim)p=v;
			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;
}

详细

Test #1:

score: 100
Accepted
time: 4ms
memory: 10700kb

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 2 
1 2 3 4 5 

result:

ok 7 numbers

Test #2:

score: 0
Accepted
time: 0ms
memory: 10584kb

input:

2 1
1 1
1 2
1 1

output:

1 2 

result:

ok 2 number(s): "1 2"

Test #3:

score: -100
Wrong Answer
time: 14ms
memory: 10640kb

input:

5 20000
1 1 1 1 1
4 5
2 1
4 3
2 3
4 4 3 1 2
4 3 4 2 1
4 4 3 2 1
1 2
3 3 2 4
1 1
4 2 3 1 4
2 4 1
3 3 2 4
3 2 4 1
1 3
2 1 3
2 2 1
4 3 2 4 1
2 3 4
4 4 2 1 3
1 4
3 2 1 4
3 2 4 1
3 4 1 2
1 3
3 4 3 1
3 3 1 4
1 2
2 3 2
1 2
3 2 3 4
2 3 4
1 3
4 2 3 4 1
2 3 4
3 2 1 4
3 3 1 4
1 1
1 3
2 2 1
2 3 4
3 1 2 4
3 3 4 ...

output:

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

result:

wrong answer 17th numbers differ - expected: '3', found: '2'