QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#156829#7103. Red Black Treeucup-team1477#AC ✓1143ms45836kbC++142.9kb2023-09-02 14:24:372023-09-02 14:55:25

Judging History

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

  • [2023-09-02 14:55:25]
  • 评测
  • 测评结果:AC
  • 用时:1143ms
  • 内存:45836kb
  • [2023-09-02 14:24:37]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
	int n=0,f=1,ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		n=n*10+ch-'0';
		ch=getchar();
	}
	return n*f;
}
int r[100005];
int fa[100005][18];
int nex[100005];
int dep[100005],qzh[100005];
int dfn[100005],cnt;
vector<int>v[100005],bq[100005];
void dfs(int x,int f)
{
	dfn[x]=++cnt;
	dep[x]=dep[f]+1;
	fa[x][0]=f;
	for(int i=1;i<=17;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
	if(r[x])nex[x]=x;
	else nex[x]=nex[f];
	for(int i=0;i<v[x].size();i++)
	{
		if(v[x][i]==f)continue;
		qzh[v[x][i]]=qzh[x]+bq[x][i];
		dfs(v[x][i],x); 
	}
}
int lca(int x,int y)
{
	if(dep[x]<dep[y])swap(x,y);
	for(int i=17;i>=0;i--)if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
	if(x==y)return x;
	for(int i=17;i>=0;i--)
	{
		if(fa[x][i]!=fa[y][i])
		{
			x=fa[x][i];
			y=fa[y][i];
		}
	}
	return fa[x][0];
}
int xw[200005],tsl;
bool inq[200005];
bool bi(int x,int y)
{
	return qzh[x]-qzh[nex[x]]>qzh[y]-qzh[nex[y]];
}
pair<int,int> pos[200005];
int ttt;
bool bibi(pair<int,int> x,pair<int,int> y)
{
	return dep[x.first]>dep[y.first];
}
int dy[200005];
int hz[200005];
multiset<int>se;
signed main()
{
	int t,n,m,q,x,y,z;
	t=read();
	for(int greg=1;greg<=t;greg++)
	{
		n=read();
		m=read();
		q=read();
		for(int i=1;i<=n;i++)r[i]=0,v[i].clear(),bq[i].clear();
		for(int i=1;i<=m;i++)
		{
			x=read();
			r[x]=1;
		}
		for(int i=1;i<=n-1;i++)
		{
			x=read();
			y=read();
			z=read();
			v[x].push_back(y);
			v[y].push_back(x);
			bq[x].push_back(z);
			bq[y].push_back(z);
		}
		dfs(1,0);
		for(int cs=1;cs<=q;cs++)
		{
			tsl=read();
			for(int i=1;i<=tsl;i++)xw[i]=read();
			if(tsl==1)
			{
				printf("0\n");
				continue;
			}
			sort(xw+1,xw+tsl+1,bi);
			ttt=0;
			int nans=0,sc=qzh[xw[1]]-qzh[nex[xw[1]]];
			for(int i=1;i<=tsl;i++)
			{
				int sth=lca(xw[1],xw[i]);
				if(dep[sth]<=dep[nex[xw[1]]]||dep[sth]<=dep[nex[xw[i]]])
				{
					nans=max(nans,qzh[xw[i]]-qzh[nex[xw[i]]]);
					continue;
				}
				pos[++ttt]=make_pair(sth,i);
				pos[++ttt]=make_pair(nex[xw[i]],-i);
			}
			sort(pos+1,pos+ttt+1,bibi);
			hz[ttt+1]=0;
			for(int i=ttt;i>=1;i--)
			{
				if(pos[i].second<0)
				{
					hz[i]=hz[i+1];
					continue;
				}
				int sth=xw[pos[i].second];
				hz[i]=max(hz[i+1],qzh[sth]-qzh[nex[sth]]);
			}
			se.clear();
			for(int i=1;i<=ttt;i++)
			{
				int sth=0;
				if(pos[i].second>0)sth=xw[pos[i].second];
				else sth=xw[-pos[i].second];
				int npos=pos[i].first;
				if(pos[i].second<0)
				{
					se.erase(se.find(qzh[sth]));
					nans=max(nans,qzh[sth]-qzh[nex[sth]]);
				}
				else
				{
					se.insert(qzh[sth]);
				}
				int tmax=0;
				if(!se.empty())tmax=(*(--se.end()));
				sc=min(sc,max(max(nans,hz[i+1]),tmax-qzh[npos]));
			}
			printf("%lld\n",sc);
		}
	}
	return 0;
}

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

詳細信息

Test #1:

score: 100
Accepted
time: 4ms
memory: 14144kb

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: 1143ms
memory: 45836kb

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