QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#198402#7103. Red Black TreeFlamireAC ✓1700ms29764kbC++142.7kb2023-10-03 13:40:432023-10-03 13:40:43

Judging History

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

  • [2023-10-03 13:40:43]
  • 评测
  • 测评结果:AC
  • 用时:1700ms
  • 内存:29764kb
  • [2023-10-03 13:40:43]
  • 提交

answer

#include <bits/stdc++.h>
#define N 100011
#define ll long long
using namespace std;
int n,m,q,fa[N][21],dfn[N],siz[N],dep[N],clk,rn[N],rred[N],k[N],t;bool red[N];ll wdep[N],w[N];
struct edge{int v,w,next;edge(){}edge(int _v,int _w,int _next){v=_v;w=_w;next=_next;}}e[N*2];int head[N],sz;
void init(){memset(head,-1,sizeof(head));sz=0;}void insert(int u,int v,int w){e[++sz]=edge(v,w,head[u]);head[u]=sz;}
void dfs0(int u,int f)
{
	fa[u][0]=f;for(int i=1;i<=20;++i)fa[u][i]=fa[fa[u][i-1]][i-1];
	for(int i=head[u];~i;i=e[i].next)if(e[i].v^f)dep[e[i].v]=dep[u]+1,wdep[e[i].v]=wdep[u]+e[i].w,dfs0(e[i].v,u);
}
void dfs(int u,int f,int rt)
{
	dfn[u]=++clk;siz[u]=1;rred[u]=rt;
	for(int i=head[u];~i;i=e[i].next)if(!red[e[i].v]&&e[i].v^f)dfs(e[i].v,u,rt),siz[u]+=siz[e[i].v];
}
struct sgt
{
	ll mx[N*4];
	void pushup(int x){mx[x]=max(mx[x<<1],mx[x<<1|1]);}
	void build(int l,int r,int x)
	{
		if(l==r){mx[x]=0;return;}
		build(l,l+r>>1,x<<1);build((l+r>>1)+1,r,x<<1|1);pushup(x);
	}
	void add(int k,ll p,int L=1,int R=n,int x=1)
	{
		if(L==R){mx[x]=p;return;}
		if(k<=L+R>>1)add(k,p,L,L+R>>1,x<<1);else add(k,p,(L+R>>1)+1,R,x<<1|1);pushup(x);
	}
	ll query(int l,int r,int L=1,int R=n,int x=1)
	{
		if(l>r)return 0;
		if(l<=L&&R<=r)return mx[x];ll ans=0;
		if(l<=L+R>>1)ans=max(ans,query(l,r,L,L+R>>1,x<<1));if(r>L+R>>1)ans=max(ans,query(l,r,(L+R>>1)+1,R,x<<1|1));return ans;
	}
}sgt1,sgt2;
pair<ll,ll> solve(int y)
{
	ll res1=sgt1.query(dfn[y],dfn[y]+siz[y]-1)-wdep[y];
	ll res2=max(sgt2.query(1,dfn[y]-1),sgt2.query(dfn[y]+siz[y],n));
	return make_pair(res1,res2);
}
int lca(int u,int v)
{
	if(dep[u]<dep[v])swap(u,v);for(int i=20;~i;--i)if(dep[u]-(1<<i)>=dep[v])u=fa[u][i];if(u==v)return u;
	for(int i=20;~i;--i)if(fa[u][i]^fa[v][i])u=fa[u][i],v=fa[v][i];return fa[u][0];
}
set<int> st;
int main()
{
	scanf("%d",&t);while(t--)
	{
		scanf("%d%d%d",&n,&m,&q);for(int i=1;i<=n;++i)head[i]=-1,red[i]=0;sz=0;rn[0]=0;clk=0;
		for(int i=1;i<=m;++i){int x;scanf("%d",&x);red[x]=1;rn[++rn[0]]=x;}
		for(int i=1;i<n;++i){int u,v,w;scanf("%d%d%d",&u,&v,&w);insert(u,v,w);insert(v,u,w);}
		dfs0(1,0);
		for(int i=1;i<=m;++i)dfs(rn[i],fa[rn[i]][0],rn[i]);
		for(int i=1;i<=n;++i)w[i]=wdep[i]-wdep[rred[i]];
		while(q--)
		{
			int kn;scanf("%d",&kn);
			for(int i=1;i<=kn;++i)scanf("%d",k+i),sgt1.add(dfn[k[i]],wdep[k[i]]),sgt2.add(dfn[k[i]],w[k[i]]);
			int id=0;w[0]=-1e9;
			for(int i=1;i<=kn;++i)if(w[k[i]]>w[id])id=k[i];
			st.clear();
			for(int i=1;i<=kn;++i)st.insert(lca(k[i],id));
			ll ans=1e18;
			int cur=id;
			for(int x:st)
			{
				auto tmp=solve(x);
				ans=min(ans,max(tmp.first,tmp.second));
			}
			printf("%lld\n",ans);
			for(int i=1;i<=kn;++i)sgt1.add(dfn[k[i]],0),sgt2.add(dfn[k[i]],0);
		}
	}return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 14184kb

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: 1700ms
memory: 29764kb

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