QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#162346 | #7103. Red Black Tree | zhouhuanyi | AC ✓ | 1168ms | 51404kb | C++14 | 3.5kb | 2023-09-03 10:38:16 | 2023-09-03 10:38:16 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define N 200000
using namespace std;
const long long inf=(long long)(1e18);
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
struct reads
{
int num,data;
};
int T,n,m,q,leng,szt[N+1],depth[N+1],delta[N+1],dfn[N+1],sz[N+1],lg[N+1],fa[N+1][21],tong[N+1],length,dfns[N+1],st[N+1],lengs,dque[N+1],top;
long long A[N+1],B[N+1],dis[N+1],dp[N+1],maxn[N+1],maxn2[N+1],maxns[N+1],ans=inf;
vector<reads>E[N+1];
vector<int>ES[N+1];
bool used[N+1],vis[N+1],vst[N+1];
void add(int x,int y,int z)
{
E[x].push_back((reads){y,z}),E[y].push_back((reads){x,z});
return;
}
void dfs(int x)
{
dfn[x]=++leng,used[x]=sz[x]=1;
if (vis[x]) dis[x]=0;
for (int i=0;i<E[x].size();++i)
if (!used[E[x][i].num])
fa[E[x][i].num][0]=x,depth[E[x][i].num]=depth[x]+1,dis[E[x][i].num]=dis[x]+E[x][i].data,delta[E[x][i].num]=delta[x]+vis[E[x][i].num],dfs(E[x][i].num),sz[x]+=sz[E[x][i].num];
return;
}
bool check(int x,int y)
{
return dfn[x]<=dfn[y]&&dfn[y]<=dfn[x]+sz[x]-1;
}
bool cmp(int x,int y)
{
return dfn[x]<dfn[y];
}
int lca(int x,int y)
{
if (depth[x]<depth[y]) swap(x,y);
for (int i=lg[n];i>=0;--i)
if (depth[fa[x][i]]>=depth[y])
x=fa[x][i];
if (x==y) return x;
for (int i=lg[n];i>=0;--i)
if (fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
void dfs2(int x)
{
maxn[x]=0,dfns[x]=++lengs,szt[x]=1,st[lengs]=x;
if (vst[x]&&!vis[x]) maxn2[x]=0,maxns[x]=dis[x];
else maxn2[x]=-inf,maxns[x]=0;
for (int i=0;i<ES[x].size();++i)
{
dfs2(ES[x][i]),maxns[x]=max(maxns[x],maxns[ES[x][i]]),szt[x]+=szt[ES[x][i]];
if (delta[ES[x][i]]>delta[x]) maxn[x]=max(maxn[x],maxns[ES[x][i]]);
else maxn[x]=max(maxn[x],maxn[ES[x][i]]),maxn2[x]=max(maxn2[x],maxn2[ES[x][i]]+dis[ES[x][i]]-dis[x]);
}
dp[x]=max(maxn[x],maxn2[x]);
return;
}
int main()
{
int x,y,z,d,ds;
for (int i=2;i<=N;++i) lg[i]=lg[i>>1]+1;
T=read();
while (T--)
{
n=read(),m=read(),q=read(),leng=0;
for (int i=1;i<=n;++i) E[i].clear(),used[i]=vis[i]=vst[i]=dfn[i]=fa[i][0]=0;
for (int i=1;i<=m;++i) x=read(),vis[x]=1;
for (int i=1;i<=n-1;++i) x=read(),y=read(),z=read(),add(x,y,z);
delta[1]=vis[1],depth[1]=1,dfs(1);
for (int i=1;i<=lg[n];++i)
for (int j=1;j<=n;++j)
fa[j][i]=fa[fa[j][i-1]][i-1];
while (q--)
{
length=read(),ans=inf,lengs=0;
for (int i=1;i<=length;++i) tong[i]=read(),ES[tong[i]].clear(),vst[tong[i]]=1;
sort(tong+1,tong+length+1,cmp),top=0;
for (int i=1;i<=length;++i)
{
d=0;
while (top&&!check(dque[top],tong[i]))
{
if (d) ES[dque[top]].push_back(d);
d=dque[top],top--;
}
if (d)
{
ds=lca(d,tong[i]);
if (ds!=dque[top]) ES[ds]={d},dque[++top]=ds,dque[++top]=tong[i];
else ES[ds].push_back(d),dque[++top]=tong[i];
}
else dque[++top]=tong[i];
}
for (int i=1;i<=top-1;++i) ES[dque[i]].push_back(dque[i+1]);
dfs2(dque[1]),A[0]=B[lengs+1]=0;
for (int i=1;i<=lengs;++i)
{
if (vst[st[i]]) A[i]=max(A[i-1],dis[st[i]]);
else A[i]=A[i-1];
}
for (int i=lengs;i>=1;--i)
{
if (vst[st[i]]) B[i]=max(B[i+1],dis[st[i]]);
else B[i]=B[i+1];
}
for (int i=1;i<=lengs;++i) ans=min(ans,max(max(dp[st[i]],A[i-1]),B[dfns[st[i]]+szt[st[i]]]));
for (int i=1;i<=length;++i) vst[tong[i]]=0;
printf("%lld\n",ans);
}
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 4ms
memory: 31744kb
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: 1168ms
memory: 51404kb
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