QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#180705 | #7103. Red Black Tree | ucup-team870 | ML | 0ms | 6020kb | C++14 | 4.1kb | 2023-09-16 10:34:52 | 2023-09-16 10:34:54 |
Judging History
answer
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define For(i,j,k) for(int i=j;i<=k;++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 dfn[N],dep[N];
struct node{
int y,w;
};
vector<node> v[N];
void add(int x,int y,int z){
v[x].push_back(node{y,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; //求dfs序和深度
dep[x]=de; cnt++;
if (!pl[x]) pl[x]=cnt; q[cnt]=x;
for(auto i:v[x])
if (i.y!=fa) dfs(i.y,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){
int l=st[i-1][j],r=st[i-1][j+(1<<i-1)];
if (dep[l]<=dep[r]) st[i][j]=l;
else st[i][j]=r;
}
}
int lca(int x,int y){
x=pl[x],y=pl[y];
if (x>y) swap(x,y);
int lg=lg2[y-x+1];
int l=st[lg][x],r=st[lg][y-(1<<lg)+1];
if (dep[l]<=dep[r]) return l;
else return r;
}
void clear(int n){
For(i,1,n) pl[i]=0,v[i].clear();
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(auto i:v[x]) if (i.y!=fa){
idfs(i.y,x,d[x],y+i.w);
}
}
bool ppf[N]; int c[N];
namespace newtree{
//vector<int> v[N<<1];
int to[N<<1],nex[N<<1],head[N],e;
int st[N];
bool cmd(int x,int y){
return dfn[x]<dfn[y];
}
void add(int x,int y){
//cout<<x<<' '<<y<<endl;
//v[x].push_back(y);
to[++e]=y; nex[e]=head[x]; head[x]=e;
}
int build(){
//需要预处理dep, dfn和求lca
e=0;
sort(po+1,po+1+pl,cmd);
int top=0;
For(i,1,pl-1){
st[++top]=po[i]; st[++top]=lca(po[i],po[i+1]);
}
st[++top]=po[pl];
sort(st+1,st+top+1,cmd);
top=unique(st+1,st+top+1)-st-1;
For(i,1,top-1){
int lc=lca(st[i],st[i+1]);
add(lc,st[i+1]);
}
return st[1]; //root
}
void clear(int x){
for(int i=head[x];i;i=nex[i]) clear(to[i]);
head[x]=0;
}
long long now[N],l,r,mid; int ocnt;
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]){
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();
while(_--){
int n=read(),m=read(),k=read(),x,y,z;
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); //root记得改
idfs(1,0,0,0);
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;
}
LCA::clear(n);
memset(red,0,(n+1)<<2);
}
return 0;
}
/*
10
1 2 1 5 1 9
2 3 2 4
5 6 5 7
7 8 7 10
2
4 2 9 7 8
3 4 6 10
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 6020kb
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: -100
Memory Limit Exceeded
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...