QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#448023 | #7103. Red Black Tree | ship2077 | AC ✓ | 405ms | 24488kb | C++17 | 1.6kb | 2024-06-19 09:11:02 | 2024-06-19 09:11:03 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int M=1e5+5;
int n,m,q,idx;vector<pair<int,int>>adj[M];
int k[M],l[M],col[M],dfn[M],st[20][M];
ll ans,val[M],dep[M],mxdep[M];
int read(){
int x=0;char ch=getchar();
while (!isdigit(ch)) ch=getchar();
while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
return x;
}
int cmp(int x,int y){return dfn[x]<dfn[y]?x:y;}
void dfs(int x,int f,int lst){
if (col[x]) lst=x;
val[x]=dep[x]-dep[lst];
st[0][dfn[x]=++idx]=f;
for (auto [y,z]:adj[x]){
if (y==f) continue;
dep[y]=dep[x]+z;dfs(y,x,lst);
}
}
int lca(int x,int y){
if (x==y) return x;
if ((x=dfn[x])>(y=dfn[y])) swap(x,y);
int k=31^__builtin_clz(y-x++);
return cmp(st[k][x],st[k][y+1-(1<<k)]);
}
void solve(){
n=read();m=read();q=read();
for (int i=1;i<=n;i++) col[i]=0,adj[i].clear();
for (int i=1;i<=m;i++) col[read()]=1;
for (int i=1;i<n;i++){
int x=read(),y=read(),z=read();
adj[x].emplace_back(y,z);
adj[y].emplace_back(x,z);
} idx=0;dfs(1,0,0);
int lg=31^__builtin_clz(n);
for (int j=1;j<=lg;j++)
for (int i=1;i+(1<<j)-1<=n;i++)
st[j][i]=cmp(st[j-1][i],st[j-1][i+(1<<j-1)]);
while (q--){ m=read();ans=1ll<<60;
for (int i=1;i<=m;i++) k[i]=read(); k[m+1]=0;
sort(k+1,k+m+1,[&](int x,int y){return val[x]>val[y];});
for (int i=1;i<=m;i++) l[i]=k[i],mxdep[i]=dep[k[i]];
for (int i=2;i<=m;i++) l[i]=lca(l[i-1],l[i]),mxdep[i]=max(mxdep[i-1],mxdep[i]);
for (int i=1;i<=m;i++) ans=min(ans,max(mxdep[i]-dep[l[i]],val[k[i+1]]));
printf("%lld\n",ans);
}
}
int main(){int T=read();while (T--) solve();return 0;}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 7408kb
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: 405ms
memory: 24488kb
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