QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#179605 | #7103. Red Black Tree | cheerfulli# | TL | 1ms | 7648kb | C++20 | 2.2kb | 2023-09-14 22:55:56 | 2023-09-14 22:55:56 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
const int N=100010,INF=0x3f3f3f3f;
int n,m,q;
int h[N],e[2*N],ne[2*N],w[2*N],idx;
bool red[N];
int fa[N][18],dep[N];
LL dr[N],dis[N];
vector<int>v,st;
void add(int a,int b,int c)
{
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void bfs()
{
for(int i=1;i<=n;i++) dep[i]=INF;
dep[0]=0,dep[1]=1;
queue<int>q;
q.push(1);
while(q.size())
{
int t=q.front();
q.pop();
for(int i=h[t];~i;i=ne[i])
{
int j=e[i];
if(dep[j]>dep[t]+1)
{
dep[j]=dep[t]+1;
fa[j][0]=t;
q.push(j);
for(int k=1;k<=17;k++)
fa[j][k]=fa[fa[j][k-1]][k-1];
}
}
}
}
void dfs(int u,int fa,LL s1,LL s2)
{
dis[u]=s1;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(j==fa) continue;
if(red[j])
{
dr[j]=0;
dfs(j,u,s1+w[i],0);
}else
{
dr[j]=s2+w[i];
dfs(j,u,s1+w[i],s2+w[i]);
}
}
}
int lca(int a,int b)
{
if(dep[b]>dep[a]) swap(a,b);
for(int i=17;i>=0;i--)
if(dep[fa[a][i]]>=dep[b])
a=fa[a][i];
if(a==b) return a;
for(int i=17;i>=0;i--)
if(fa[a][i]!=fa[b][i])
{
a=fa[a][i];
b=fa[b][i];
}
return fa[a][0];
}
bool check(LL mid)
{
st.clear();
for(int i=0;i<v.size();i++)
if(dr[v[i]]>mid) st.push_back(v[i]);
if(st.size()<=1) return true;
int anc=st[0];
for(int i=1;i<st.size();i++)
anc=lca(anc,st[i]);
for(int i=0;i<st.size();i++)
if(dis[st[i]]-dis[anc]>mid) return false;
return true;
}
int main()
{
ios;
int T;
cin>>T;
while(T--)
{
cin>>n>>m>>q;
for(int i=1;i<=n;i++) h[i]=-1,red[i]=false,dr[i]=0,dis[i]=0;
idx=0;
for(int i=1;i<=m;i++)
{
int x;
cin>>x;
red[x]=true;
}
for(int i=1;i<n;i++)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);add(b,a,c);
}
bfs();
dfs(1,-1,0,0);
while(q--)
{
int k;
cin>>k;
v.clear();
for(int i=1;i<=k;i++)
{
int x;
cin>>x;
v.push_back(x);
}
LL l=0,r=1e15;
while(l<r)
{
LL mid=(l+r>>1);
if(check(mid)) r=mid;
else l=mid+1;
}
cout<<l<<endl;
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 7648kb
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...
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...