QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#163428#7103. Red Black Treeucup-team134AC ✓1123ms28660kbC++143.5kb2023-09-04 04:35:512023-09-04 04:35:51

Judging History

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

  • [2023-09-04 04:35:51]
  • 评测
  • 测评结果:AC
  • 用时:1123ms
  • 内存:28660kb
  • [2023-09-04 04:35:51]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int N=100050;
const int L=20;
bool red[N];

vector<pair<int,int>> E[N];
ll dep[N];
int lvl[N],lid[N],rid[N],tid,par[N][L];
int cnt[N];
ll best[N];

void DFS(int u,int p,int w){
	dep[u]=dep[p]+w;
	lvl[u]=lvl[p]+1;
	cnt[u]=cnt[p]+red[u];
	par[u][0]=p;
	for(int i=1;i<L;i++){
		par[u][i]=par[par[u][i-1]][i-1];
	}
	lid[u]=++tid;
	if(red[u]){
		best[u]=0;
	}else{
		best[u]=best[p]+w;
	}
	for(auto e:E[u]){
		if(e.first!=p){
			DFS(e.first,u,e.second);
		}
	}
	rid[u]=tid;
}

int LCA(int u,int v){
	if(lvl[u]<lvl[v])swap(u,v);
	for(int i=L-1;~i;i--)if(lvl[par[u][i]]>=lvl[v])u=par[u][i];
	for(int i=L-1;~i;i--)if(par[u][i]!=par[v][i])u=par[u][i],v=par[v][i];
	return u==v?v:par[v][0];
}

vector<int> G[N];
bool mark[N];
ll sol;

ll up[N],dw[N];
void DW(int u){
	for(int v:G[u]){
		DW(v);
		dw[u]=max(dw[u],dw[v]);
	}
	if(mark[u]){
		dw[u]=max(dw[u],best[u]);
	}
}
void UP(int u){
	ll fir=0,sec=0;
	for(int v:G[u]){
		if(dw[v]>fir){
			sec=fir;
			fir=dw[v];
		}else sec=max(sec,dw[v]);
	}
	for(int v:G[u]){
		ll mx=fir;
		if(dw[v]==mx){
			mx=sec;
		}
		up[v]=max(up[u],mx);
		UP(v);
	}
}

pair<ll,ll> Solve(int u){
	ll C=0;
	ll other=0;
	for(int v:G[u]){
		pair<ll,ll> tmp=Solve(v);
		if(cnt[v]==cnt[u]){
			C=max(C,tmp.first);
			other=max(tmp.second,other);
		}else{
			other=max(other,dw[v]);
		}
	}
	if(mark[u]){
		C=max(C,dep[u]);
	}
	//if(!red[u]){
		sol=min(sol,max({C-dep[u],other,up[u]}));
		//printf("u:%i  C:%lld other:%lld up:%i\n",u,C,other,up[u]);
	//}
	return {C,other};
}
int main(){
	int t;
	scanf("%i",&t);
	while(t--){
		int n,m,q;
		scanf("%i %i %i",&n,&m,&q);
		for(int i=1;i<=m;i++){
			int x;
			scanf("%i",&x);
			red[x]=true;
		}
		for(int i=1;i<n;i++){
			int u,v,w;
			scanf("%i %i %i",&u,&v,&w);
			E[u].pb({v,w});
			E[v].pb({u,w});
		}
		DFS(1,0,0);
		//printf("best: ");for(int i=1;i<=n;i++)printf("%lld ",best[i]);printf("\n");
		while(q--){
			int k;
			scanf("%i",&k);
			vector<int> nodes;
			ll ans=0;
			while(k--){
				int x;
				scanf("%i",&x);
				nodes.pb(x);
				ans+=best[x];
				//mark[x]=true;
			}
			sort(nodes.begin(),nodes.end(),[&](int u,int v){return best[u]>best[v];});
			int lca=0;
			ll mxd=0;
			for(int i=0;i<nodes.size();i++){
				if(i==0)lca=nodes[i];
				else lca=LCA(lca,nodes[i]);
				mxd=max(mxd,dep[nodes[i]]);
				ll other=(i+1==nodes.size())?0:best[nodes[i+1]];
				ans=min(ans,max(mxd-dep[lca],other));
			}
			/*k=nodes.size();
			for(int i=1;i<k;i++){
				nodes.pb(LCA(nodes[i],nodes[i-1]));
			}
			//printf("Nodes ext: ");for(int x:nodes)printf("%i ",x);printf("\n");
			sort(nodes.begin(),nodes.end(),[&](int u,int v){return lid[u]<lid[v];});
			nodes.erase(unique(nodes.begin(),nodes.end()),nodes.end());
			//printf("Nodes unq: ");for(int x:nodes)printf("%i ",x);printf("\n");
			stack<int> stk;
			for(int x:nodes){
				while(stk.size()&&rid[stk.top()]<lid[x]){
					stk.pop();
				}
				if(stk.size()){
					G[stk.top()].pb(x);
				}
				stk.push(x);
			}
			while(stk.size()>1){
				stk.pop();
			}
			int root=stk.top();
			sol=ans;
			DW(root);
			UP(root);
			Solve(root);
			ans=sol;*/
			printf("%lld\n",ans);

			/*for(int x:nodes){
				mark[x]=false;
				G[x].clear();
				dw[x]=up[x]=0;
			}*/
		}

		for(int i=1;i<=n;i++){
			E[i].clear();
			red[i]=false;
		}
		tid=0;
	}
	return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 1123ms
memory: 28660kb

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