QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#157882 | #7103. Red Black Tree | ucup-team918# | AC ✓ | 592ms | 38452kb | C++17 | 4.1kb | 2023-09-02 15:57:33 | 2023-09-02 15:57:33 |
Judging History
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