QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#163428 | #7103. Red Black Tree | ucup-team134 | AC ✓ | 1123ms | 28660kb | C++14 | 3.5kb | 2023-09-04 04:35:51 | 2023-09-04 04:35:51 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=100050;
const int L=20;
bool red[N];
vector<pair<int,int>> E[N];
ll dep[N];
int lvl[N],lid[N],rid[N],tid,par[N][L];
int cnt[N];
ll best[N];
void DFS(int u,int p,int w){
dep[u]=dep[p]+w;
lvl[u]=lvl[p]+1;
cnt[u]=cnt[p]+red[u];
par[u][0]=p;
for(int i=1;i<L;i++){
par[u][i]=par[par[u][i-1]][i-1];
}
lid[u]=++tid;
if(red[u]){
best[u]=0;
}else{
best[u]=best[p]+w;
}
for(auto e:E[u]){
if(e.first!=p){
DFS(e.first,u,e.second);
}
}
rid[u]=tid;
}
int LCA(int u,int v){
if(lvl[u]<lvl[v])swap(u,v);
for(int i=L-1;~i;i--)if(lvl[par[u][i]]>=lvl[v])u=par[u][i];
for(int i=L-1;~i;i--)if(par[u][i]!=par[v][i])u=par[u][i],v=par[v][i];
return u==v?v:par[v][0];
}
vector<int> G[N];
bool mark[N];
ll sol;
ll up[N],dw[N];
void DW(int u){
for(int v:G[u]){
DW(v);
dw[u]=max(dw[u],dw[v]);
}
if(mark[u]){
dw[u]=max(dw[u],best[u]);
}
}
void UP(int u){
ll fir=0,sec=0;
for(int v:G[u]){
if(dw[v]>fir){
sec=fir;
fir=dw[v];
}else sec=max(sec,dw[v]);
}
for(int v:G[u]){
ll mx=fir;
if(dw[v]==mx){
mx=sec;
}
up[v]=max(up[u],mx);
UP(v);
}
}
pair<ll,ll> Solve(int u){
ll C=0;
ll other=0;
for(int v:G[u]){
pair<ll,ll> tmp=Solve(v);
if(cnt[v]==cnt[u]){
C=max(C,tmp.first);
other=max(tmp.second,other);
}else{
other=max(other,dw[v]);
}
}
if(mark[u]){
C=max(C,dep[u]);
}
//if(!red[u]){
sol=min(sol,max({C-dep[u],other,up[u]}));
//printf("u:%i C:%lld other:%lld up:%i\n",u,C,other,up[u]);
//}
return {C,other};
}
int main(){
int t;
scanf("%i",&t);
while(t--){
int n,m,q;
scanf("%i %i %i",&n,&m,&q);
for(int i=1;i<=m;i++){
int x;
scanf("%i",&x);
red[x]=true;
}
for(int i=1;i<n;i++){
int u,v,w;
scanf("%i %i %i",&u,&v,&w);
E[u].pb({v,w});
E[v].pb({u,w});
}
DFS(1,0,0);
//printf("best: ");for(int i=1;i<=n;i++)printf("%lld ",best[i]);printf("\n");
while(q--){
int k;
scanf("%i",&k);
vector<int> nodes;
ll ans=0;
while(k--){
int x;
scanf("%i",&x);
nodes.pb(x);
ans+=best[x];
//mark[x]=true;
}
sort(nodes.begin(),nodes.end(),[&](int u,int v){return best[u]>best[v];});
int lca=0;
ll mxd=0;
for(int i=0;i<nodes.size();i++){
if(i==0)lca=nodes[i];
else lca=LCA(lca,nodes[i]);
mxd=max(mxd,dep[nodes[i]]);
ll other=(i+1==nodes.size())?0:best[nodes[i+1]];
ans=min(ans,max(mxd-dep[lca],other));
}
/*k=nodes.size();
for(int i=1;i<k;i++){
nodes.pb(LCA(nodes[i],nodes[i-1]));
}
//printf("Nodes ext: ");for(int x:nodes)printf("%i ",x);printf("\n");
sort(nodes.begin(),nodes.end(),[&](int u,int v){return lid[u]<lid[v];});
nodes.erase(unique(nodes.begin(),nodes.end()),nodes.end());
//printf("Nodes unq: ");for(int x:nodes)printf("%i ",x);printf("\n");
stack<int> stk;
for(int x:nodes){
while(stk.size()&&rid[stk.top()]<lid[x]){
stk.pop();
}
if(stk.size()){
G[stk.top()].pb(x);
}
stk.push(x);
}
while(stk.size()>1){
stk.pop();
}
int root=stk.top();
sol=ans;
DW(root);
UP(root);
Solve(root);
ans=sol;*/
printf("%lld\n",ans);
/*for(int x:nodes){
mark[x]=false;
G[x].clear();
dw[x]=up[x]=0;
}*/
}
for(int i=1;i<=n;i++){
E[i].clear();
red[i]=false;
}
tid=0;
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 11556kb
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: 1123ms
memory: 28660kb
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