QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#159173 | #7103. Red Black Tree | ucup-team870# | AC ✓ | 1444ms | 37640kb | C++17 | 4.9kb | 2023-09-02 17:35:04 | 2023-09-02 17:35:06 |
Judging History
answer
#include <bits/stdc++.h>
#define For(i,l,r) for(int i=l; i<=r; i++)
using namespace std;
int read(){
int x=0,fh=1; char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if (ch=='-') fh=1;
for(;isdigit(ch);ch=getchar()) x=x*10+(ch^48);
return x*fh;
}
const int N=1e5+5;
int to[N<<1],nex[N<<1],head[N],e,dfn[N],dep[N]; long long ew[N<<1];
void add(int x,int y,int z){
to[++e]=y; nex[e]=head[x]; head[x]=e; ew[e]=z;
}
namespace LCA{
int dfnn,lg2[N<<1],q[N<<1],pl[N],st[18][N<<1],cnt;
void dfs(int x,int fa,int de){
dfn[x]=++dfnn;
dep[x]=de; cnt++;
if (!pl[x]) pl[x]=cnt; q[cnt]=x;
for(int i=head[x];i;i=nex[i]){
if (to[i]!=fa) dfs(to[i],x,de+1),q[++cnt]=x;
}
}
void init(int n,int root){
For(i,2,n<<1) lg2[i]=lg2[i/2]+1;
dfs(root,0,1);
For(i,1,cnt) st[0][i]=q[i];
For(i,1,lg2[cnt])
For(j,1,cnt-(1<<i)+1)
if (dep[ st[i-1][j] ]<=dep[ st[i-1][j+(1<<i-1)] ]) st[i][j]=st[i-1][j];
else st[i][j]=st[i-1][j+(1<<i-1)];
}
int lca(int x,int y){
int lg;
x=pl[x]; y=pl[y];
if (x>y) lg=x,x=y,y=lg;
lg=lg2[y-x+1];
if (dep[ st[lg][x] ]<=dep[ st[lg][y-(1<<lg)+1] ]) return st[lg][x];
else return st[lg][y-(1<<lg)+1];
}
void clear(int n){
For(i,1,n) pl[i]=0; cnt=0; dfnn=0;
}
}
using LCA::lca;
int po[N],pl;
int red[N],d[N]; long long vw[N],dw[N];
void idfs(int x,int fa,int dd,long long y){
vw[x]=y;
if (red[x]) d[x]=x; else d[x]=dd;
dw[x]=-vw[d[x]]+vw[x]; //cout<<"!!"<<vw[x]<<' '<<vw[d[x]]<<endl;
for(int i=head[x];i;i=nex[i]) if (to[i]!=fa){
idfs(to[i],x,d[x],y+ew[i]);
}
}
bool ppf[N]; int c[N];
namespace newtree{
int to[N<<2],nex[N<<2],head[N],e;
int st[N],top;
long long l,r,mid,ocnt,now[N<<2];
bool cmd(int x,int y){
return dfn[x]<dfn[y];
}
void add(int x,int y){
//cout<<"#"<<' '<<x<<' '<<y<<endl;
to[++e]=y; nex[e]=head[x]; head[x]=e;
}
int build(){
e=0; top=0;
sort(po+1,po+1+pl,cmd);
st[++top]=po[1];
int cnt=1;
while(cnt<pl){
//cout<<'~'<<cnt<<endl;
int now=po[++cnt],lc=lca(st[top],now); //cout<<'~'<<cnt<<' '<<lc<<endl;
while(dep[lc]<dep[ st[top-1] ]){
add(st[top-1],st[top]); --top;
}
if (lc==st[top]) st[++top]=now;
else if (dep[lc]>dep[ st[top-1] ]){
add(lc,st[top]); --top; st[++top]=lc; st[++top]=now;
}
else if (lc==st[top-1]){
add(lc,st[top]); --top; st[++top]=now;
}
}
while(top>1){
add(st[top-1],st[top]); --top;
}
return st[1];
}
void clear(int x){
for(int i=head[x];i;i=nex[i]) clear(to[i]);
head[x]=0;
}
bool dfs(int x,int fa){
now[x]=0; c[x]=0;
if (ppf[x]) ++c[x];
bool redf;
for(int i=head[x];i;i=nex[i]) if (to[i]!=fa){
int y=to[i]; redf=dfs(y,x);
if (!redf&&c[y]) c[x]+=c[y],now[x]=max(now[x],now[y]-vw[x]+vw[y]);
}
if (red[x]) {c[x]=0; return 1;}
else if (c[x]&&now[x]-vw[fa]+vw[x]>mid) {c[x]=0; ++ocnt; return 1;}
else return 0;
}
void work(){
int root=build();
//dp
l=0,r=0; r=r*r;
For(i,1,pl) r=max(r,dw[po[i]]);
while(l<r){
mid=(l+r)>>1; ocnt=0;
dfs(root,0);
if (ocnt<=1) r=mid;
else l=mid+1;
}
printf("%lld\n",l); //cout<<endl;
clear(root);
}
}
bool pf[N];
int main(){
int _=read(),x,y,z;
while(_--){
int n=read(),m=read(),k=read();
//clear
For(i,1,n) head[i]=0,red[i]=0; e=0;
LCA::clear(n);
//init
For(i,1,m) x=read(),red[x]=1;
For(i,1,n-1) x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z);
LCA::init(n,1);
//cout<<"##"<<endl;
idfs(1,0,0,0);
//cout<<"@@"<<endl;
//
while(k--){
//build
pl=read();
For(i,1,pl) po[i]=read(),ppf[po[i]]=pf[ po[i] ]=1;
int tmp=pl;
For(i,1,tmp) if (!pf[ d[po[i]] ]){
pf[ d[po[i]] ]=1; po[++pl]=d[po[i]];
}
//cout<<"!!"<<pl<<endl;
//For(i,1,pl) cout<<po[i]<<' '; cout<<endl;
newtree::work();
For(i,1,pl) ppf[po[i]]=pf[po[i]]=0;
}
}
}
/*
9
12 2 4
1 9
1 2 1
2 3 4
3 4 3
3 5 2
2 6 2
6 7 1
6 8 2
2 9 5
9 10 2
9 11 3
1 12 10
3 3 7 8
4 4 5 7 8
4 7 8 10 11
3 4 5 12
3 2 3
1 2
1 2 1
1 3 1
1 1
2 1 2
3 1 2 3
9 3 1
1 4 5
1 2 1
2 3 1
3 4 1
3 5 1
4 6 0
4 7 0
5 8 0
5 9 0
5 2 6 7 8 9
*/
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 22308kb
input:
2 12 2 4 1 9 1 2 1 2 3 4 3 4 3 3 5 2 2 6 2 6 7 1 6 8 2 2 9 5 9 10 2 9 11 3 1 12 10 3 3 7 8 4 4 5 7 8 4 7 8 10 11 3 4 5 12 3 2 3 1 2 1 2 1 1 3 1 1 1 2 1 2 3 1 2 3
output:
4 5 3 8 0 0 0
result:
ok 7 lines
Test #2:
score: 0
Accepted
time: 1444ms
memory: 37640kb
input:
522 26 1 3 1 1 4 276455 18 6 49344056 18 25 58172365 19 9 12014251 2 1 15079181 17 1 50011746 8 9 2413085 23 24 23767115 22 2 26151339 26 21 50183935 17 14 16892041 9 26 53389093 1 20 62299200 24 18 56114328 11 2 50160143 6 26 14430542 16 7 32574577 3 16 59227555 3 15 8795685 4 12 5801074 5 20 57457...
output:
148616264 148616264 0 319801028 319801028 255904892 317070839 1265145897 1265145897 1072765445 667742619 455103436 285643094 285643094 285643094 317919339 0 785245841 691421476 605409472 479058444 371688030 303203698 493383271 919185207 910180170 919185207 121535083 181713164 181713164 181713164 181...
result:
ok 577632 lines
Extra Test:
score: 0
Extra Test Passed