QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#160436#7103. Red Black Treeucup-team1732#AC ✓602ms35552kbC++143.1kb2023-09-02 20:27:102023-09-02 20:27:10

Judging History

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

  • [2023-09-02 20:27:10]
  • 评测
  • 测评结果:AC
  • 用时:602ms
  • 内存:35552kb
  • [2023-09-02 20:27:10]
  • 提交

answer

// created:  Sep/02/2023 19:46:11
#include<cstdio>
#include<vector>
#include<algorithm>
#define F(i,l,r) for(int i=l,i##_end=r;i<i##_end;++i)
using namespace std;
template<typename T>void readmain(T &x)
{
	bool neg=false;
	unsigned int c=getchar();
	for(;(c^48)>9;c=getchar())if(c=='-')neg=true;
	for(x=0;(c^48)<10;c=getchar())x=(x<<3)+(x<<1)+(c^48);
	if(neg)x=-x;
}
template<typename T>T& read(T &x){readmain(x);return x;}
template<typename T,typename ...Tr>void read(T &x,Tr&... r){readmain(x);read(r...);}
constexpr int N=1e5+5,LogN=20;
constexpr long long LLINF=0x3f3f3f3f3f3f3f3f;
int tt,n,mm,q,fa[N],sr[N],dfn[N],ind,idfn[N],st[N][LogN],logn,dep[N],nd[N],ndc;
int sta[N],top,vt[N];
long long dis[N],sd[N];
bool red[N],sl[N];
vector<pair<int,int>> adj[N];
vector<int> ch[N];
void dfs1(int u)
{
	if(red[u])++sr[u],dis[u]=0;
	idfn[dfn[u]=ind++]=u;
	for(const pair<int,int> &vw:adj[u])
	{
		const int &v=vw.first,&w=vw.second;
		if(v==fa[u])continue;
		fa[v]=u;
		sr[v]=sr[u];
		dis[v]=dis[u]+w;
		sd[v]=sd[u]+w;
		st[ind-1][0]=dfn[u];
		dep[v]=dep[u]+1;
		dfs1(v);
	}
}
long long mx[N],up[N],ans,dmx[N],amx[N];
void dfs2(int u)
{
	amx[u]=-LLINF;
	dmx[u]=0;
	if(sl[u])mx[u]=dis[u],amx[u]=0;
	else mx[u]=0;
	for(const int &v:ch[u])
	{
		dfs2(v);
		mx[u]=max(mx[u],mx[v]);
		if(sr[v]==sr[u])dmx[u]=max(dmx[u],dmx[v]),amx[u]=max(amx[u],amx[v]+sd[v]-sd[u]);
		else dmx[u]=max(dmx[u],mx[v]);
	}
}
void dfs3(int u)
{
	long long mxv[2]={max(up[u],sl[u]?dis[u]:0),0};
	for(const int &v:ch[u])
	{
		if(mx[v]>mxv[0])mxv[1]=mxv[0],mxv[0]=mx[v];
		else if(mx[v]>mxv[1])mxv[1]=mx[v];
	}
	for(const int &v:ch[u])up[v]=mxv[mxv[0]==mx[v]];
	ans=min(ans,max(up[u],max(dmx[u],amx[u])));
	for(const int &v:ch[u])dfs3(v);
}
int lca(int u,int v)
{
	if(u==v)return u;
	u=dfn[u];v=dfn[v];
	if(u>v)swap(u,v);
	int k=31-__builtin_clz(v-u);
	return idfn[min(st[u][k],st[v-(1<<k)][k])];
}
int main()
{
	read(tt);
	while(tt--)
	{
		ind=0;
		read(n,mm,q);
		F(i,0,n)red[i]=false;
		F(i,0,mm)
		{
			int r_;--read(r_);
			red[r_]=true;
		}
		F(i,0,n-1)
		{
			int u,v,w;read(u,v,w);--u,--v;
			adj[u].emplace_back(v,w);
			adj[v].emplace_back(u,w);
		}
		dfs1(0);
		logn=0;
		while((2<<logn)<n)++logn;
		F(i,0,logn)F(j,0,n-(2<<i))st[j][i+1]=min(st[j][i],st[j+(1<<i)][i]);
		while(q--)
		{
			int k;read(k);
			F(i,0,k)sl[--read(vt[i])]=true;
			sort(vt,vt+k,[](int u,int v){return dfn[u]<dfn[v];});
			top=0;sta[top++]=0;
			ndc=0;nd[ndc++]=0;
			F(i,!vt[0],k)
			{
				int u=vt[i],w=lca(sta[top-1],u),dd=dep[w];
				while(dep[sta[top-1]]>dd)
				{
					if(dep[sta[top-2]]>=dd)
					{
						--top;
						ch[sta[top-1]].emplace_back(sta[top]);
					}
					else
					{
						ch[w].emplace_back(sta[top-1]);
						sta[top-1]=w;
						nd[ndc++]=w;
						break;
					}
				}
				sta[top++]=u;
				nd[ndc++]=u;
			}
			--top;
			while(top)ch[sta[top-1]].emplace_back(sta[top]),--top;
			ans=LLINF;
			dfs2(0);
			dfs3(0);
			F(i,0,ndc)ch[nd[i]].clear();
			F(i,0,k)sl[vt[i]]=false;
			printf("%lld\n",ans);
		}
		F(i,0,n)adj[i].clear();
	}
	return 0;
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 16204kb

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: 602ms
memory: 35552kb

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