QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#266665 | #7103. Red Black Tree | UtopianZ# | AC ✓ | 762ms | 35508kb | C++14 | 2.3kb | 2023-11-26 16:26:59 | 2023-11-26 16:27:00 |
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],fa[maxn];
int lid[maxn],dfn[maxn<<1],tot=0,lg2[maxn<<1],stt[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;
stt[u]=++tot;dfn[tot]=u;
for(auto v:to[u])if(v.fi^f){
dist[v.fi]=dist[u]+v.se;dfs(v.fi,u);
dfn[++tot]=u;
}
return ;
}
int st[maxn<<1][20];
void build(){
lg2[0]=-1;
for(int i=1;i<=tot;i++)st[i][0]=dfn[i],lg2[i]=lg2[i>>1]+1;
for(int i=1;i<20;i++)for(int j=1;j+(1<<i)-1<=tot;j++){
if(dep[st[j][i-1]]<dep[st[j+(1<<(i-1))][i-1]])st[j][i]=st[j][i-1];
else st[j][i]=st[j+(1<<(i-1))][i-1];
}
return ;
}
int lca(int u,int v){
int l=stt[u],r=stt[v];
if(l>r)swap(l,r);
int lg=lg2[r-l+1];
if(dep[st[l][lg]]<dep[st[r-(1<<lg)+1][lg]])return st[l][lg];
return st[r-(1<<lg)+1][lg];
}
bool check(long long mid){
int nlca=0;
// cout<<"mid:"<<mid<<endl;
for(int i=1;i<=dsiz;i++)if(dist[toquer[i]]-dist[lid[toquer[i]]]>mid){
// cout<<toquer[i]<<endl;
if(!nlca)nlca=toquer[i];
else nlca=lca(nlca,toquer[i]);
}
// cout<<nlca<<endl;
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();
tot=0;
for(int i=1;i<=n;i++){
to[i].clear();isr[i]=false;dep[i]=dist[i]=dfn[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();
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){
long long 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;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 9964kb
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: 762ms
memory: 35508kb
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