QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#157882#7103. Red Black Treeucup-team918#AC ✓592ms38452kbC++174.1kb2023-09-02 15:57:332023-09-02 15:57:33

Judging History

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

  • [2023-09-02 15:57:33]
  • 评测
  • 测评结果:AC
  • 用时:592ms
  • 内存:38452kb
  • [2023-09-02 15:57:33]
  • 提交

answer

//Was yea ra,rra yea ra synk sphilar yor en me exec hymme METAFALICA waath!
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#include<bits/stdc++.h>
using namespace std;
#define rg register
#define ll long long
#define ull unsigned ll
#define lowbit(x) (x&(-x))
#define djq 998244353
const double eps=1e-10;
const short sint=0x3f3f;
const int inf=0x3f3f3f3f;
const ll linf=0x3f3f3f3f3f3f3f3f;
const double alpha=0.73;
const double PI=acos(-1);
inline void file(){
	freopen("1.in","r",stdin);
	freopen("1.out","w",stdout);
}
char buf[1<<21],*p1=buf,*p2=buf;
inline int getc(){
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,(1<<20)+5,stdin),p1==p2)?EOF:*p1++;
}
//#define getc getchar
inline ll read(){
	rg ll ret=0,f=0;char ch=getc();
    while(!isdigit(ch)){if(ch==EOF)exit(0);if(ch=='-')f=1;ch=getc();}
    while(isdigit(ch)){ret=ret*10+ch-48;ch=getc();}
    return f?-ret:ret;
}
inline void rdstr(char* s){
	char ch=getc();
	while(ch<33||ch>126) ch=getc();
	while(ch>=33&&ch<=126) (*s++)=ch,ch=getc();
}
#define ep emplace
#define epb emplace_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define it iterator
#define mkp make_pair
#define naive return 0*puts("Yes")
#define angry return 0*puts("No")
#define fls fflush(stdout)
#define rep(i,a) for(rg int i=1;i<=a;++i)
#define per(i,a) for(rg int i=a;i;--i)
#define rep0(i,a) for(rg int i=0;i<=a;++i)
#define per0(i,a) for(rg int i=a;~i;--i)
#define szf sizeof
typedef vector<int> vec;
typedef pair<int,int> pii;
struct point{ int x,y; point(int x=0,int y=0):x(x),y(y) {} inline bool operator<(const point& T)const{ return x^T.x?x<T.x:y<T.y; }; };
inline int ksm(int base,int p){int ret=1;while(p){if(p&1)ret=1ll*ret*base%djq;base=1ll*base*base%djq,p>>=1;}return ret;}
inline void pls(int& x,const int k){ x=(x+k>=djq?x+k-djq:x+k); }
inline int add(const int a,const int b){ return a+b>=djq?a+b-djq:a+b; }
inline void sub(int& x,const int k){ x=(x-k<0?x-k+djq:x-k); }
inline int inc(const int a,const int b){ return a<b?a-b+djq:a-b; }
inline void ckmn(int& x,const int k){ x=(k<x?k:x); }
inline void ckmx(int& x,const int k){ x=(k>x?k:x); }
inline void ckmn(ll& x,const ll k){ x=(k<x?k:x); }
inline void ckmx(ll& x,const ll k){ x=(k>x?k:x); }
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());



int n,m,q,col[100005];
vector<pii> e[100005];
int pos[100005],dep[100005],id[200005],tim;
ll dis[100005];
void dfs(int x,int fa){
	dep[x]=dep[fa]+1; pos[x]=++tim; id[tim]=x; 
	for(auto [y,z]:e[x]) if(y!=fa) dis[y]=dis[x]+z,dfs(y,x),id[++tim]=x;
}
int st[200005][21],lg[200005];
void init(){
	lg[0]=-1;
	rep(i,tim) st[i][0]=id[i],lg[i]=lg[i>>1]+1;
	for(rg int j=1;j<=lg[tim];++j)
		for(rg int i=1;i+(1<<j)-1<=tim;++i)
			st[i][j]=(dep[st[i][j-1]]<dep[st[i+(1<<(j-1))][j-1]]?st[i][j-1]:st[i+(1<<(j-1))][j-1]);
}
inline int lca(int x,int y){
	const int l=min(pos[x],pos[y]),r=max(pos[x],pos[y]),lgl=lg[r-l+1];
	return dep[st[l][lgl]]<dep[st[r-(1<<lgl)+1][lgl]]?st[l][lgl]:st[r-(1<<lgl)+1][lgl];
}
ll mn[100005];
void dfs1(int x,int fa,ll nw){
	if(col[x]) nw=0;
	mn[x]=nw;
	for(auto [y,z]:e[x]){
		if(y==fa) continue;
		dfs1(y,x,min(nw+z,linf));
	}
}
int v[100005];
signed mian(){
	n=read(),m=read(),q=read();
	rep(i,n) e[i].clear(),col[i]=0;
	rep(i,m){
		const int x=read();
		col[x]=1;
	}
	rep(i,n-1){
		const int x=read(),y=read(),z=read();
		e[x].epb(y,z),e[y].epb(x,z);
	}
	tim=0,dfs(1,0),init();
	dfs1(1,0,linf);
	while(q--){
		const int k=read();
		rep(i,k) v[i]=read();
		sort(v+1,v+1+k,[&](const int& x,const int& y){
			return mn[x]>mn[y];
		});
		v[k+1]=0;
		int nw(0); ll ans(linf),mx(0);
		for(rg int i=1,j=1;i<=k+1;++i){
			while(j<=k&&mn[v[j]]>mn[v[i]]){
				if(nw==0) nw=v[j];
				else nw=lca(nw,v[j]);
				ckmx(mx,dis[v[j]]);
				++j;
			}
			//printf("[%d %d]=(%d,%d)\n",i,j,nw.fi,nw.se);
			ckmn(ans,max(mx-dis[nw],mn[v[i]]));
		}
		printf("%lld\n",ans);
	}
	return 0;
}
signed main(){
	//file();
	int _=read();
	while(_--) mian();
	return 0;
}
/*

*/

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

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 12060kb

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: 592ms
memory: 38452kb

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