QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#175698#7103. Red Black Treepengpeng_fudan#AC ✓760ms37824kbC++142.5kb2023-09-10 21:37:562023-09-10 21:37:56

Judging History

你现在查看的是最新测评结果

  • [2023-09-10 21:37:56]
  • 评测
  • 测评结果:AC
  • 用时:760ms
  • 内存:37824kb
  • [2023-09-10 21:37:56]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ull=unsigned long long;
using ll=long long;
int n,m,q;
bool flag[100010];
vector<pair<int,int>> tr[100010];
int fa_rd[100010];
ll len[100010][18];
int fa[100010][18];
int dep[100010];
ll bla_len[100010];
void build(){
    int u,v,w;
    for(int i=1;i<=n-1;i++){
        cin>>u>>v>>w;
        tr[u].push_back({v,w});
        tr[v].push_back({u,w});
    }
}
void dfs(int u,int v,int ln,int t){
    dep[u]=dep[v]+1;
    fa[u][0]=v;len[u][0]=ln;
    for(int i=1;i<18;i++){
        fa[u][i]=fa[fa[u][i-1]][i-1];
        len[u][i]=len[u][i-1]+len[fa[u][i-1]][i-1];
    }
    if(flag[u]==1)  t=u;
    else fa_rd[u]=t;
    for(auto i:tr[u]){
        if(i.first==v)  continue;
        dfs(i.first,u,i.second,t);
    }
}   
int lca(int x,int y){
    if(dep[x]<dep[y])   swap(x,y);
    for(int i=17;i>=0;i--){
        if(dep[fa[x][i]]>=dep[y])   x=fa[x][i];
    }
    if(x==y)    return x;
    for(int i=17;i>=0;i--){
        if(fa[x][i]!=fa[y][i])  x=fa[x][i],y=fa[y][i];
    }
    return fa[x][0];
} 
ll get_len(int x,int f){
    ll ans=0;
    for(int i=17;i>=0;i--){
        if(dep[fa[x][i]]>=dep[f]){
            ans+=len[x][i];
            x=fa[x][i];
        }
    }
    return ans;
}
vector<int> v;
void query(){
    v.clear();
    v.resize(1);
    int k,num;
    cin>>k;
    for(int i=1;i<=k;i++){
        cin>>num;
        if(!flag[num])  v.push_back(num);   
    }
    sort(v.begin()+1,v.end(),[&](int a,int b){return bla_len[a]>bla_len[b];});
    int sz=v.size()-1;
    if(sz<=1){cout<<0<<'\n';return ;}
    ll ans=bla_len[v[2]];
    int pre_la=v[1];
    for(int i=2;i<=sz;i++){
        if(fa_rd[v[i]]!=fa_rd[v[1]])  break;
        int la=lca(pre_la,v[i]);
        if(i!=sz)   ans=min(ans,max(bla_len[v[i+1]],get_len(v[1],la)));
        else ans=min(ans,get_len(v[1],la));
        pre_la=la;
    }
    cout<<ans<<'\n';
}
void solve() {
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++){
        tr[i].clear();
        fill(fa[i],fa[i]+18,0);
        fill(len[i],len[i]+18,0);
        flag[i]=fa_rd[i]=bla_len[i]=dep[i]=0;
    }
    int num;
    for(int i=1;i<=m;i++){
        cin>>num;
        flag[num]=1;
    }
    build();
    dfs(1,1,0,1);
    //for(int i=1;i<=n;i++)   cout<<fa_rd[i]<<'\n';
    for(int i=1;i<=n;i++){
        if(!flag[i])   bla_len[i]=get_len(i,fa_rd[i]);  
    }
    for(int i=1;i<=q;i++)   query();
}

int main() {
    ios::sync_with_stdio(0),cin.tie(0);
    int _ = 1; 
    cin >> _;
    while(_--) solve();
    return 0;
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 10452kb

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: 760ms
memory: 37824kb

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