QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#351865 | #7211. Attack | Naganohara_Yoimiya | WA | 4ms | 10916kb | C++14 | 4.5kb | 2024-03-12 16:42:55 | 2024-03-12 16:42:55 |
Judging History
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'