QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#170504 | #7103. Red Black Tree | xianggui# | WA | 1944ms | 57104kb | C++20 | 5.9kb | 2023-09-09 15:24:00 | 2023-09-09 15:24:02 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int T;
int n,m,q,k;
int dfn[100010],timee;
int key[100010];
int a[100010<<2],tot,root;
bool red[100010],kk[100010];
vector<pair<int, ll> > ed[100010],eed[100010];
int fa[100010][21],deep[100010];
ll sum[100010][21];
ll cost[100010];
void dfs(int x,int f)
{
dfn[x]=++timee;
for(int i=1;i<=20;i++)
{
fa[x][i]=fa[fa[x][i-1]][i-1];
sum[x][i]=sum[fa[x][i-1]][i-1]+sum[x][i-1];
}
for(auto i:ed[x])
{
int v=i.first;
ll val=i.second;
if(v==f) continue;
deep[v]=deep[x]+1;
fa[v][0]=x;
sum[v][0]=val;
dfs(v, x);
}
}
void dfs1(int x,int f,ll ss)
{
if(red[x]) ss=0;
cost[x]=ss;
for(auto i:ed[x])
{
int v=i.first;
ll val=i.second;
if(v==f) continue;
dfs1(v, x, ss+val);
}
}
int lca(int x,int y)
{
if(deep[x]<deep[y]) swap(x,y);
for(int i=20;i>=0;i--)
{
int xx=fa[x][i];
if(deep[xx]>=deep[y])
{
x=xx;
}
}
if(x==y) return x;
for(int i=20;i>=0;i--)
{
int xx=fa[x][i];
int yy=fa[y][i];
if(xx!=yy)
{
x=xx;
y=yy;
}
}
return fa[x][0];
}
ll getsum(int x,int y)
{
ll res=0;
for(int i=20;i>=0;i--)
{
int xx=fa[x][i];
if(deep[xx]>=deep[y])
{
res+=sum[x][i];
x=xx;
}
}
return res;
}
bool cmp(int x,int y)
{
return dfn[x]<dfn[y];
}
int id;
ll ans;
ll high[100010];
int fff[100010];
bool maxvis[100010];
int sikey[100010];
void DFS(int x)
{
if(x==id) maxvis[x]=1;
if(kk[x]) sikey[x]++;
for(auto i:eed[x])
{
int v=i.first;
ll val=i.second;
fff[v]=x;
DFS(v);
sikey[x]+=sikey[v];
maxvis[x]|=maxvis[v];
high[x]=max(high[x], high[v]+val);
}
}
int lefkey[100010],silef;
void DFS1(int x)
{
for(auto i:eed[x])
{
int v=i.first;
ll val=i.second;
if(maxvis[v])
{
DFS1(v);
if(kk[v]) lefkey[++silef]=v;
break;
}
}
for(auto i:eed[x])
{
int v=i.first;
ll val=i.second;
if(maxvis[v]) continue;
DFS1(v);
if(kk[v]) lefkey[++silef]=v;
}
}
ll backmaxx[100010];
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
cout.tie(0);
cin>>T;
while(T--)
{
cin>>n>>m>>q;
timee=0;
for(int i=1;i<=n;i++)
{
red[i]=0;
ed[i].clear();
dfn[i]=0;
}
for(int i=1;i<=m;i++)
{
int x;
cin>>x;
red[x]=1;
}
for(int i=1;i<n;i++)
{
int x,y;
ll z;
cin>>x>>y>>z;
ed[x].push_back(make_pair(y, z));
ed[y].push_back(make_pair(x, z));
}
deep[1]=1;
dfs(1,0);
dfs1(1, 0, 0);
while(q--)
{
cin>>k;
// cout<<"cost:\n";
for(int i=1;i<=k;i++)
{
cin>>key[i];
kk[key[i]]=1;
// cout<<cost[key[i]]<<" ";
}
// puts("");
tot=0;
sort(key+1,key+k+1,cmp);
for(int i=1;i<k;i++)
{
int tem=lca(key[i],key[i+1]);
a[++tot]=key[i];
a[++tot]=tem;
}
a[++tot]=key[k];
sort(a+1,a+1+tot,cmp);
tot=unique(a+1,a+1+tot)-(a+1);
// cout<<"vt:\n";
for(int i=1;i<=tot;i++)
{
// cout<<a[i]<<" ";
eed[a[i]].clear();
fff[a[i]]=0;
maxvis[a[i]]=0;
high[a[i]]=0;
sikey[a[i]]=0;
}
// puts("");
// puts("");
root=a[1];
// cout<<"bt:\n";
for(int i=1;i<tot;i++)
{
int tem=lca(a[i],a[i+1]);
ll val=getsum(a[i+1], tem);
// cout<<tem<<" "<<a[i+1]<<endl;
eed[tem].push_back(make_pair(a[i+1], val));
}
id=0;
ans=0;
// cout<<"!\n";
for(int i=1;i<=k;i++)
{
// cout<<key[i]<<" "<<cost[key[i]]<<endl;
if(cost[key[i]]>ans)
{
ans=cost[key[i]];
id=key[i];
}
}
// cout<<id<<endl;
// cout<<ans<<endl;
silef=0;
DFS(root);
DFS1(root);
backmaxx[silef+1]=0;
// for(int i=1;i<=silef;i++)
// {
// cout<<lefkey[i]<<" ";
// }
// puts("");
// puts("");
for(int i=silef;i>=1;i--)
{
backmaxx[i]=max(backmaxx[i+1], cost[lefkey[i]]);
}
while(id!=0)
{
if(!red[id])
{
int nowsi=sikey[id];
ll backmax=backmaxx[nowsi+1];
// cout<<id<<endl;
// cout<<backmax<<" "<<high[id]<<endl;
ans=min(ans, max(backmax, high[id]));
}
id=fff[id];
}
for(int i=1;i<=k;i++) kk[key[i]]=0;
cout<<ans<<'\n';
}
}
return 0;
}
/*
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
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 13812kb
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
Wrong Answer
time: 1944ms
memory: 57104kb
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 66903787 319801028 319801028 255904892 317070839 1265145897 1265145897 1072765445 667742619 455103436 285643094 285643094 285643094 317919339 57081624 785245841 691421476 605409472 479058444 371688030 303203698 493383271 919185207 910180170 919185207 121535083 181713164 181713164...
result:
wrong answer 3rd lines differ - expected: '0', found: '66903787'