QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#225831 | #7103. Red Black Tree | fzj2007# | TL | 1ms | 10204kb | C++14 | 3.8kb | 2023-10-25 10:16:00 | 2023-10-25 10:16:00 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T &x){
x=0;
char ch=getchar();
bool flag=0;
while(ch>'9'||ch<'0') flag=flag||ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
x=flag?-x:x;
}
template<typename T,typename ...Args>inline void read(T &x,Args &...args){
read(x),read(args...);
}
template<typename T>inline void prt(T x){
if(x>9) prt(x/10);
putchar(x%10+'0');
}
template<typename T>inline void put(T x){
if(x<0) putchar('-'),x=-x;
prt(x);
}
template<typename T>inline void put(char ch,T x){
put(x),putchar(ch);
}
template<typename T,typename ...Args>inline void put(char ch,T x,Args ...args){
put(ch,x),put(ch,args...);
}
#define N 100005
#define inf 0x3f3f3f3f
int n,m,q,col[N];
int dfn[N],idx,st[N][20],lg[N],dep[N],pre[N],fir[N],fath[N];
vector<pair<int,int>> e[N];
vector<int> g[N];
inline int Min(int x,int y){
return dep[x]<dep[y]?x:y;
}
inline void dfs(int x,int fa){
dfn[x]=++idx,st[idx][0]=x,dep[x]=dep[fa]+1;
fir[x]=col[x]?x:fir[fa],fath[x]=fa;
for(auto v:e[x])
if(v.first!=fa) pre[v.first]=pre[x]+v.second,dfs(v.first,x);
}
inline int lca(int x,int y){
if(x==y) return x;
x=dfn[x],y=dfn[y];
if(x>y) swap(x,y);
x++;
int k=lg[y-x+1];
return fath[Min(st[x][k],st[y-(1<<k)+1][k])];
}
int k,pos[N],vis[N];
int sta[N],tp;
vector<int> used;
inline void build(){
tp=0,sta[++tp]=1,used.emplace_back(1);
for(int i=1;i<=k;i++){
if(sta[tp]==pos[i]) continue;
int f=lca(sta[tp],pos[i]);
while(tp>1&&dep[sta[tp-1]]>=dep[f]) g[sta[tp-1]].emplace_back(sta[tp]),tp--;
if(sta[tp]!=f) g[f].emplace_back(sta[tp]),sta[tp]=f,used.emplace_back(f);
sta[++tp]=pos[i],used.emplace_back(pos[i]);
}
while(tp>1) g[sta[tp-1]].emplace_back(sta[tp]),tp--;
}
int A[N],B[N],ans;
inline void dp(int x){
for(auto v:g[x]) dp(v);
if(vis[x]&&!col[x]) B[x]=A[x]=0;
else B[x]=-inf,A[x]=0;
for(auto v:g[x]){
A[x]=max(A[x],A[v]);
if(dep[fir[v]]<dep[x]) B[x]=max(B[x],B[v]+pre[v]-pre[x]);
else A[x]=max(A[x],B[v]+pre[v]-pre[fir[v]]);
}
}
inline void solve(int x,int lftans){
ans=min(ans,max(lftans,max(A[x],B[x])));
int num=0,pos=0;
for(auto v:g[x]) num+=B[v]!=-inf&&!fir[v],pos=v;
if(!g[x].size()||num>=2) return;
if(num){
int maxa=0;
for(auto v:g[x])
if(v!=pos) maxa=max(maxa,max(A[v],B[v]+pre[v]-pre[fir[v]]));
solve(pos,max(lftans,maxa));
return;
}
vector<int> L(g[x].size()),R(g[x].size());
for(int i=0;i<g[x].size();i++){
int v=g[x][i];
L[i]=max(A[v],B[v]+pre[v]-pre[fir[v]]);
if(i) L[i]=max(L[i],L[i-1]);
}
for(int i=(int)g[x].size()-1;i>=0;i--){
int v=g[x][i];
R[i]=max(A[v],B[v]+pre[v]-pre[fir[v]]);
if(i<(int)g[x].size()-1) R[i]=max(R[i],R[i+1]);
}
for(int i=0;i<g[x].size();i++){
int maxa=0,v=g[x][i];
if(i) maxa=max(maxa,L[i-1]);
if(i<(int)g[x].size()-1) maxa=max(maxa,R[i+1]);
solve(v,max(lftans,maxa));
}
// for(auto pos:g[x]){
// int maxa=0;
// for(auto v:g[x])
// if(v!=pos) maxa=max(maxa,max(A[v],B[v]+pre[v]-pre[fir[v]]));
// solve(pos,max(lftans,maxa));
// }
}
inline void solve(){
read(n,m,q);
for(int i=1,x;i<=m;i++) read(x),col[x]=1;
for(int i=1,u,v,w;i<n;i++)
read(u,v,w),e[u].emplace_back(v,w),e[v].emplace_back(u,w);
dfs(1,0);
for(int j=1;j<=lg[n];j++)
for(int i=1;i+(1<<j)-1<=n;i++) st[i][j]=Min(st[i][j-1],st[i+(1<<j-1)][j-1]);
while(q--){
read(k);
for(int i=1;i<=k;i++) read(pos[i]),vis[pos[i]]=1;
sort(pos+1,pos+k+1,[](const int &x,const int &y){return dfn[x]<dfn[y];});
build();
ans=inf,dp(1),solve(1,0);
put('\n',ans);
for(int i=1;i<=k;i++) vis[pos[i]]=0;
for(auto v:used) g[v].clear();
}
}
inline void clear(){
for(int i=1;i<=n;i++) col[i]=0,e[i].clear();
idx=0;
}
int T;
int main(){
for(int i=2;i<N;i++) lg[i]=lg[i>>1]+1;
read(T);
while(T--) solve(),clear();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 10204kb
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 1061109567 1061109567 1061109567 667742619 455103436 285643094 285643094 285643094 317919339 0 785245841 691421476 605409472 479058444 371688030 303203698 493383271 919185207 910180170 919185207 121535083 166647862 166647862 166647862 166...