QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#266595 | #7103. Red Black Tree | UtopianZ# | TL | 2ms | 8368kb | C++14 | 2.1kb | 2023-11-26 15:39:28 | 2023-11-26 15:39:28 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int sum=0,fh=1;
char c=getchar();
while(c>'9'||c<'0'){
if(c=='-')fh=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
sum*=10;
sum+=c-'0';
c=getchar();
}
return sum*fh;
}
#define maxn 100009
#define pb push_back
#define mp make_pair
#define fi first
#define se second
int n,m,q,t,dep[maxn],hs[maxn],ltop[maxn],fa[maxn],siz[maxn];
int lid[maxn];
long long dist[maxn];
vector<pair<int ,int > > to[maxn];
int toquer[maxn],dsiz;
bool isr[maxn];
void dfs(int u,int f=0){
if(isr[u])lid[u]=u;
else lid[u]=lid[f];
fa[u]=f;
dep[u]=dep[f]+1;siz[u]=1;
for(auto v:to[u])if(v.fi^f){
dist[v.fi]=dist[u]+v.se;dfs(v.fi,u);
siz[u]+=siz[v.fi];
if(siz[hs[u]]<siz[v.fi])hs[u]=v.fi;
}
return ;
}
void build(int u,int f=0){
if(u==hs[f])ltop[u]=ltop[f];
else ltop[u]=u;
for(auto v:to[u])if(v.fi^f)build(v.fi,u);
return ;
}
int lca(int u,int v){
while(ltop[u]^ltop[v]){
if(dep[ltop[u]]>dep[ltop[v]])swap(u,v);
v=fa[ltop[v]];
}
if(dep[u]>dep[v])swap(u,v);
return u;
}
bool check(long long mid){
int nlca=0;
for(int i=1;i<=dsiz;i++)if(dist[toquer[i]]-dist[lid[toquer[i]]]>mid){
if(!nlca)nlca=toquer[i];
else nlca=lca(nlca,toquer[i]);
}
for(int i=1;i<=dsiz;i++)if(dist[toquer[i]]-max(dist[lid[toquer[i]]],dist[nlca])>mid)return false;
return true;
}
void solve(){
n=read();m=read();q=read();
for(int i=1;i<=n;i++){
to[i].clear();isr[i]=false;ltop[i]=hs[i]=dep[i]=0;
}
for(int i=1;i<=m;i++)isr[read()]=true;
for(int i=1;i<n;i++){
int u=read(),v=read(),w=read();
to[u].pb(mp(v,w));to[v].pb(mp(u,w));
}
dfs(1);build(1);
for(int i=1;i<=q;i++){
dsiz=read();
for(int j=1;j<=dsiz;j++)toquer[j]=read();
long long l=0,r=1e14,ans=1e14;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid))ans=mid,r=mid-1;
else l=mid+1;
}
printf("%lld\n",ans);
}
return ;
}
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
t=read();
while(t--){
solve();
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 8368kb
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: -100
Time Limit Exceeded
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...