QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#175666#7103. Red Black Treepengpeng_fudan#WA 580ms32596kbC++142.5kb2023-09-10 21:11:482023-09-10 21:11:49

Judging History

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

  • [2023-09-10 21:11:49]
  • 评测
  • 测评结果:WA
  • 用时:580ms
  • 内存:32596kb
  • [2023-09-10 21:11:48]
  • 提交

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});
    }
}
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])   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=0;
    for(int i=2;i<=sz;i++){
        if(fa_rd[v[i]]!=fa_rd[v[1]])  break;
        int la=lca(v[1],v[i]);
        if(pre_la!=0&&lca(la,pre_la)==pre_la)   la=pre_la;
        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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 10228kb

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: 580ms
memory: 32596kb

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:

6077529
6077529
0
305453775
305453775
245618151
0
348105753
348105753
248085638
248085638
137401084
0
157488312
0
0
0
576622652
209311252
289748355
301002858
0
0
217950554
121945382
0
121945382
0
0
0
0
0
0
40333527
40333527
40333527
28987516
0
87750905
87750905
87750905
87750905
87750905
87750905
87...

result:

wrong answer 1st lines differ - expected: '148616264', found: '6077529'