QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#684972 | #9373. Query on Tree | wyxqwq | WA | 42ms | 58316kb | C++14 | 7.6kb | 2024-10-28 16:51:48 | 2024-10-28 16:51:48 |
Judging History
answer
#include<bits/stdc++.h>
#define vectorwyx maze
namespace vectorwyx{
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mk make_pair
#define sml(x,y) (x=min(x,y))
#define big(x,y) (x=max(x,y))
#define ll long long
#define uint unsigned
#define ull unsigned long long
#define umap unordered_map
#define db double
#define fo(i,x,y) for(int i=(x);i<=(y);++i)
#define go(i,x,y) for(int i=(x);i>=(y);--i)
#define ptc putchar
#define gtc getchar
#define emp emplace
#define re return
#define co continue
#define brk break
#define HH (ptc('\n'))
#define bctz __builtin_ctz
#define bclz __builtin_clz
#define bppc __builtin_popcount
using namespace std;
ll seed=chrono::system_clock::now().time_since_epoch().count();
mt19937 rnd(seed);
inline int rm(int x,int y){return (int)(rnd()%(y-x+1ll)+x);}
inline int read(){signed ch=getchar();int x=0,f=1;while(!isdigit(ch)){if(ch==(int)('-'))f=-1;ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline ll llread(){signed ch=getchar();ll x=0,f=1;while(!isdigit(ch)){if(ch==(int)('-'))f=-1;ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
template<typename T> void out(T *a,int l,int r){fo(i,l,r) cout<<*(a+i)<<' ';puts("");}
const int N=2e5+5,K=9;
const ll inf=1e18;
vector<int> e[N];
int bfn[N],tb,bod[N],dod[N],bL[N][K+2],bR[N][K+2],fa[N][K+2],dL[N],dR[N],td,n;
ll a[N];
void init(){
fo(i,1,K) fa[1][i]=0;
fo(i,1,n) e[i].clear(),fa[i][0]=i;
fo(i,1,n) fo(j,0,K) bL[i][j]=n+1,bR[i][j]=0;
tb=td=0;
}
void dfs1(int x){
for(int i:e[x]) if(i!=fa[x][1]){
fo(j,1,K) fa[i][j]=fa[x][j-1];
dfs1(i);
}
}
void bfs(){
queue<int> q;q.push(1);
while(!q.empty()){
int x=q.front();q.pop();
bfn[x]=++tb;bod[tb]=x;
fo(i,0,K) if(fa[x][i]) sml(bL[fa[x][i]][i],bfn[x]),big(bR[fa[x][i]][i],bfn[x]);
for(int i:e[x]) if(i!=fa[x][1]) q.push(i);
}
// cout<<"bfn:";out(bfn,1,n);
}
void dfs2(int x){
if(!bR[x][K]) re;
dL[x]=++td;dod[td]=x;
for(int i:e[x]) if(i!=fa[x][1]) dfs2(i);
dR[x]=td;
}
struct Seg{
#define ls (x<<1)
#define rs (x<<1|1)
#define mid ((l+r)>>1)
struct Node{
ll mx,tag;
Node(){mx=-inf,tag=0;}
void upd(ll &k){mx+=k,tag+=k;}
}tr[N<<2];
void ps(int x){tr[x].mx=max(tr[ls].mx,tr[rs].mx);}
void pd(int x){
ll &k=tr[x].tag;
tr[ls].upd(k);
tr[rs].upd(k);
k=0;
}
void build(ll *a,int x,int l,int r){
if(l>r) re;
// printf("build(%d,%d,%d)\n",x,l,r);
if(l==r){
tr[x].mx=a[l];
tr[x].tag=0;
re;
}
build(a,ls,l,mid);
build(a,rs,mid+1,r);
ps(x);
}
void update(int x,int l,int r,int L,int R,ll v){
if(L>R) re;
// printf("update(%d,%d,%d,%d,%d,%lld)\n",x,l,r,L,R,v);
if(l>=L&&r<=R){
tr[x].upd(v);
re;
}
pd(x);
if(L<=mid) update(ls,l,mid,L,R,v);
if(R>mid) update(rs,mid+1,r,L,R,v);
ps(x);
}
void set(int x,int l,int r,int aim,ll v){
if(l==r){tr[x].mx=v;re;}
pd(x);
if(aim<=mid) set(ls,l,mid,aim,v);
else set(rs,mid+1,r,aim,v);
ps(x);
}
ll ask(int x,int l,int r,int L,int R){
if(L>R) re -inf;
if(l>=L&&r<=R) re tr[x].mx;
pd(x);
if(R<=mid) re ask(ls,l,mid,L,R);
if(L>mid) re ask(rs,mid+1,r,L,R);
re max(ask(ls,l,mid,L,R),ask(rs,mid+1,r,L,R));
}
};
ll tmp[N];
namespace Tree_b{
Seg b;
void build(){fo(i,1,n) tmp[i]=a[bod[i]];b.build(tmp,1,1,n);}
void update(int l,int r,ll v){b.update(1,1,n,l,r,v);}
ll ask(int l,int r){
re b.ask(1,1,n,l,r);
// ll ret=-inf;fo(i,l,r) big(ret,b[i]);
// printf("Tree_b::ask(%d,%d)=%lld\n",l,r,ret);
// re ret;
}
}
namespace Tree_d{
Seg tag,mx;
void build(){
fo(i,1,td) tmp[i]=0;
tag.build(tmp,1,1,td);
fo(i,1,n) tmp[i]=-inf;
fo(i,1,n) if(bR[i][K])
fo(j,bL[i][K],bR[i][K]) big(tmp[dL[i]],a[bod[j]]);
mx.build(tmp,1,1,td);
// cout<<"Tree_d::mx:";out(mx,1,n);
}
void update(int l,int r,ll v){
// printf("update(%d,%d,%lld)\n",l,r,v);
// fo(i,l,r) tag[i]+=v,mx[i]+=v;
tag.update(1,1,td,l,r,v);
mx.update(1,1,td,l,r,v);
}
ll ask(int l,int r){
re mx.ask(1,1,td,l,r);
// ll ret=-inf;fo(i,l,r) big(ret,mx[i]);
// printf("ask(%d,%d)=%lld\n",l,r,ret);
// re ret;
}
void clr_tag(int x){
Tree_b::update(bL[x][K],bR[x][K],tag.ask(1,1,td,dL[x],dL[x]));
tag.set(1,1,td,dL[x],0);
// tag[dL[x]]=0;
}
void reset(int x){
mx.set(1,1,td,dL[x],Tree_b::ask(bL[x][K],bR[x][K]));
// mx[dL[x]]=Tree_b::ask(bL[x][K],bR[x][K]);
}
}
void gao(int l,int r,int v){
// printf("gao(%d,%d,%d)\n",l,r,v);
if(l>r) re;
int x=bod[l];
assert(fa[x][K]==fa[bod[r]][K]);
x=fa[x][K];
if(!x){Tree_b::update(l,r,v);re;}
Tree_d::clr_tag(x);
Tree_b::update(l,r,v);
Tree_d::reset(x);
}
ll nbor(int x,int k,int v){
// printf("nbor(%d,%d,%d)\n",x,k,v);
if(!fa[x][1]){
ll ret=-inf;
fo(i,0,k){
if(!bR[x][i]) break;
gao(bL[x][i],bR[x][i],v);
big(ret,Tree_b::ask(bL[x][i],bR[x][i]));
}
re ret;
}
// puts("qwq");
gao(bL[x][k],bR[x][k],v);
// puts("qaq");
if(k==0) re Tree_b::ask(bfn[x],bfn[x]);
gao(bL[x][k-1],bR[x][k-1],v);
ll ret=max(Tree_b::ask(bL[x][k],bR[x][k]),Tree_b::ask(bL[x][k-1],bR[x][k-1]));
re max(ret,nbor(fa[x][1],k-1,v));
}
void solve(){
cin>>n;int q=read();init();
fo(i,1,n) a[i]=llread();
fo(i,2,n){
int x=read(),y=read();
e[x].pb(y),e[y].pb(x);
}
dfs1(1);
bfs();
td=0;dfs2(1);
// fo(i,1,n){cout<<i<<":";fo(j,0,K) printf("[%d,%d] ",bL[i][j],bR[i][j]);HH;}
// fo(i,1,n) printf("[%d,%d] ",dL[i],dR[i]);HH;
// fo(i,0,K) printf("[%d,%d] ",bL[5][i],bR[5][i]);HH;printf("[%d,%d]\n",dL[5],dR[5]);
Tree_b::build();Tree_d::build();
// cout<<"mx:";out(Tree_d::mx,1,td);
while(q--){
int o=read(),x=read();
if(o==3){
int v=read();
ll ans=-inf;
fo(i,0,K-1){
if(!bR[x][i]) break;
gao(bL[x][i],bR[x][i],v);
big(ans,Tree_b::ask(bL[x][i],bR[x][i]));
}
if(bR[x][K]) Tree_d::update(dL[x],dR[x],v),big(ans,Tree_d::ask(dL[x],dR[x]));
cout<<ans<<'\n';
co;
}
int k=read(),v=read();
if(o==1){
ll ans=-inf;
if(bR[x][k]) gao(bL[x][k],bR[x][k],v),big(ans,Tree_b::ask(bL[x][k],bR[x][k]));
fo(i,1,k){
if(!fa[x][i]) break;
int l=bL[fa[x][i]][k-i],r=bR[fa[x][i]][k-i];
if(!r) co;
if(i==k){gao(l,r,v);big(ans,Tree_b::ask(l,r));break;}
int L=bL[fa[x][i-1]][k-i-1],R=bR[fa[x][i-1]][k-i-1];
if(!R){gao(l,r,v),big(ans,Tree_b::ask(l,r));co;}
if(l<L) gao(l,L-1,v),big(ans,Tree_b::ask(l,L-1));
if(r>R) gao(R+1,r,v),big(ans,Tree_b::ask(R+1,r));
}
if(ans==-inf) puts("GG");
else cout<<ans<<'\n';
co;
}
cout<<nbor(x,k,v)<<'\n';
}
}
signed main(){
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
int T=read();
while(T--) solve();
return 0;
}
}
/*
1
5 5
1 2 1 3 2
1 2
2 3
2 4
4 5
2 2 1 0
1 2 1 3
3 4 -5
2 5 2 3
3 2 -1
-------------------------------------------------
*/
signed main(){re vectorwyx::main();}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 58196kb
input:
1 5 5 1 2 1 3 2 1 2 2 3 2 4 4 5 2 2 1 0 1 2 1 3 3 4 -5 2 5 2 3 3 2 -1
output:
3 6 1 5 4
result:
ok 5 lines
Test #2:
score: 0
Accepted
time: 37ms
memory: 58116kb
input:
10000 3 9 42973045452542 34994498886390 -91733395797555 1 3 1 2 1 1 5 -71952967 3 1 -816873082 1 1 5 -842437577 2 3 7 254550528 3 3 -854082700 2 3 2 699808309 3 3 554885567 1 2 7 595565507 1 3 0 -318374053 3 2 -63158159333100 77264362049163 -99188430131116 1 2 3 2 2 2 4 -305866230 3 1 -549738403 3 5...
output:
GG 42972228579460 GG 42972483129988 -91734812202809 42973182938297 -91733557508933 GG -91733875882986 77264056182933 77263506444530 7065382376488 7065749360235 7066534912965 -85115611272570 -85114714781312 96492412785032 -20428913156111 -20428197540063 96491742171666 -14945310996805 96491180203461 -...
result:
ok 200000 lines
Test #3:
score: -100
Wrong Answer
time: 42ms
memory: 58316kb
input:
10000 4 32 -1057044448491 -93293078803919 -24212938548357 74427756948193 1 3 1 2 3 4 3 1 -82365883 1 2 9 -730670945 2 4 2 -618745828 2 1 2 774032949 3 3 6733210 3 3 -843683844 3 1 327410390 3 1 -865685600 1 4 6 -951367966 3 2 107763506 1 3 2 721870187 2 3 3 -530847597 2 2 1 451029291 3 2 231297873 3...
output:
74427674582310 GG 74427055836482 74427829869431 74427836602641 74426992918797 74427320329187 74426454643587 GG -93292817648557 -93292095778370 74425923795990 -1057589620769 -93291944298803 74425228504438 74425430401539 -93291936231808 74425906008467 GG -1058067327518 74424997886529 74424370598990 74...
result:
wrong answer 196th lines differ - expected: '92593553133044', found: '92593120115062'