QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#153198#7103. Red Black TreePhantomThreshold#AC ✓950ms28820kbC++202.5kb2023-08-29 16:42:572023-08-29 16:42:58

Judging History

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

  • [2023-08-29 16:42:58]
  • 评测
  • 测评结果:AC
  • 用时:950ms
  • 内存:28820kb
  • [2023-08-29 16:42:57]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int maxd=16;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	mt19937 rng(58);
	int T=10;
	cin>>T;
	while(T--)
	{
		int n,m,q;
		n=q=100000;
		m=1000;
		cin>>n>>m>>q;
		vector<int> a(n+5);
		vector<vector<pair<int,int>>> G(n+5);
		vector<long long> len(n+5),rlen(n+5);
		vector<int> pa(n+5),dfn(n+5),dfnend(n+5),dep(n+5);
		for(int i=1;i<=m;i++)
		{
			int x;
			x=rng()%n+1;
			cin>>x;
			a[x]=1;
		}
		for(int i=1;i<n;i++)
		{
			int u,v,w;
			u=i+1,v=i,w=rng()%1000000000+1;
			cin>>u>>v>>w;
			G[u].emplace_back(v,w);
			G[v].emplace_back(u,w);
		}
		int ind=0;
		function<void(int)> dfs=[&](int u)
		{
			dfn[u]=++ind;
			if(a[u])rlen[u]=0;
			for(auto [v,w]:G[u])
			{
				if(not dfn[v])
				{
					pa[v]=u;
					dep[v]=dep[u]+1;
					len[v]=len[u]+w;
					rlen[v]=rlen[u]+w;
					dfs(v);
				}
			}
			dfnend[u]=ind;
		};
		len[1]=dep[1]=1;
		dfs(1);
//		long long maxlen=*max_element(rlen.begin(),rlen.end());
//		cerr<<"end dfs "<<endl;
		vector<vector<int>> jmp(maxd+5,vector<int>(n+5));
		for(int i=1;i<=n;i++)jmp[0][i]=pa[i];
		for(int d=1;d<=maxd;d++)
			for(int i=1;i<=n;i++)
				jmp[d][i]=jmp[d-1][jmp[d-1][i]];
		/*
		auto anc=[&](int u,long long k)
		{
			long long target=max(len[u]-k,1ll);
//			cerr<<"anc "<<u<<' '<<k<<' '<<target<<endl;
			for(int d=maxd;d>=0;d--)
			{
				if(len[jmp[d][u]]>=target)
					u=jmp[d][u];
			}
			return u;
		};
		*/
		auto getlca=[&](int u,int v)
		{
			if(dep[u]<dep[v])swap(u,v);
			for(int d=maxd;d>=0;d--)
			{
				if(dep[jmp[d][u]]>=dep[v])
					u=jmp[d][u];
			}
			if(u==v)return u;
			for(int d=maxd;d>=0;d--)
			{
				if(jmp[d][u]!=jmp[d][v])
					u=jmp[d][u],v=jmp[d][v];
			}
			return pa[u];
		};
//		cerr<<"end jmp"<<endl;
//		for(int i=1;i<=n;i++)cerr<<i<<' '<<dfn[i]<<' '<<dfnend[i]<<' '<<len[i]<<' '<<rlen[i]<<' '<<pa[i]<<endl;
		vector<int> t(n+5);
		while(q--)
		{
			int k;
			k=2;
			cin>>k;
			vector<pair<long long,int>> srt;
			for(int i=1;i<=k;i++)
			{
				t[i]=rng()%n+1;
				cin>>t[i];
				srt.emplace_back(rlen[t[i]],t[i]);
			}
			sort(srt.begin(),srt.end(),greater<pair<long long,int>>());
			int lca=-1;
			long long maxl=0,ans=1e14;
			srt.emplace_back(0,0);
			for(unsigned i=0;i+1<srt.size();i++)
			{
				int u=srt[i].second;
				if(lca==-1)lca=u;
				else lca=getlca(lca,u);
				maxl=max(maxl,len[u]);
				ans=min(ans,max(maxl-len[lca],srt[i+1].first));
			}
			cout<<ans<<"\n";
		}
//		cerr<<"end query"<<endl;
	}
	
	return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 950ms
memory: 28820kb

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