QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#162346#7103. Red Black TreezhouhuanyiAC ✓1168ms51404kbC++143.5kb2023-09-03 10:38:162023-09-03 10:38:16

Judging History

你现在查看的是最新测评结果

  • [2023-09-03 10:38:16]
  • 评测
  • 测评结果:AC
  • 用时:1168ms
  • 内存:51404kb
  • [2023-09-03 10:38:16]
  • 提交

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,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

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