QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#214628#7103. Red Black TreeYangmf#WA 807ms66976kbC++173.2kb2023-10-14 22:04:202023-10-14 22:04:20

Judging History

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

  • [2023-10-14 22:04:20]
  • 评测
  • 测评结果:WA
  • 用时:807ms
  • 内存:66976kb
  • [2023-10-14 22:04:20]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
#define error           \
    {                   \
        cout << "No\n"; \
        return;         \
    }
#define all(x) (x.begin(), x.end())
const int N = 1e6 + 10;
int a[N];
int n, m, q;
bool f[N];
vector<pii> ed[N];
pii v[N];
int val[N],fat[N];
void dfs(int x,int fa){

    for(auto t:ed[x]){

        int y=t.first,z=t.second;
        if(y==fa) continue;
        if(f[y]) {

            val[y]=0;
            fat[y]=y;
        } else {

            val[y]=val[x]+z;
            fat[y]=fat[x];
        }
        dfs(y,x);
    }       
}
bool cmp(pii x,pii y){

    if(x.first!=y.first) return x.first>y.first;
    else return x.second>y.second;
}
int d[N],dist[N],fa[N][30];
int ht;
void  bfs(){

    queue<int> q;
    q.push(1);
    d[1]=1;
    dist[1]=0;
    while(q.size()){

        int x=q.front(); q.pop();
        for(auto t:ed[x]){

            int y=t.first,z=t.second;
            if(d[y]) continue;
            d[y]=d[x]+1;
            dist[y]=dist[x]+z;
            fa[y][0]=x;
            for(int j=1;j<=ht;j++){

                fa[y][j]=fa[fa[y][j-1]][j-1];
            }
            q.push(y);
        }
    }
}
int lca(int x,int y){

    if(d[x]>d[y]) swap(x,y);
    for(int i=ht;i>=0;i--){

        if(d[fa[y][i]]>=d[x]) y=fa[y][i];
    }
    if(x==y) return x;
    for(int i=ht;i>=0;i--){

        if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
    }   
    return fa[x][0];
}
const int inf=1e18;
pii me[N];
void solve()
{
    cin>>n>>m>>q;
    ht=(int)(log(n)/log(2))+1;
    for(int i=1;i<=m;i++){

        int x;
        cin>>x;
        f[x]=1;
    }

    for(int i=1;i<n;i++){

        int x,y,z;
        cin>>x>>y>>z;
        ed[x].push_back({y,z});
        ed[y].push_back({x,z});
    }
    bfs();
    val[1]=0;
    fat[1]=1;
    dfs(1,0);
    // for(int i=1;i<=n;i++){

    //     cout<<val[i]<<" ";
    // }
    // cout<<"\n";
    while(q--){

        int k;
        cin>>k;
        // cout<<"*****\n";
        for(int i=1;i<=k;i++) {

            int x;
            cin>>x;
            v[i] = { val[x],fat[x] };
            me[i]={val[x],x};
            // pt.push_back();
            // cout<<x<<" "<<val[x]<<"\n";
        }
        sort(v+1,v+k+1,cmp);
        sort(me+1,me+k+1,cmp);
        v[k+1]={-1,0};
        int ans;
        if(k==1) {

            cout<<0<<"\n";
            continue;
        } else {

            ans=v[2].first;
        }
        int ss=v[1].second;
        int pre=me[1].second;
        for(int i=2;i<=k;i++){
            // cout<<pre<<"\n";
            pii t=v[i];
            int y=t.first,z=t.second;
            if(z!=ss) break;
            pre=lca(pre,me[i].second);
            ans=min(ans,max(v[i+1].first,v[1].first-(dist[pre]-dist[ss])));
        }
        cout<<ans<<"\n";
    }
    for(int i=1;i<=n;i++){

        ed[i].clear();
        f[i]=0;
    }
}
signed main()
{

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {

        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 807ms
memory: 66976kb

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
493591722
493591722
471453091
493591722
1717669833
1717669833
1312647007
1168076167
587526565
285643094
285643094
285643094
317919339
0
916794839
717968006
605409472
479058444
371688030
307718947
566052472
1287389114
910180170
1124931652
121535083
316895493
316895493
316895493
...

result:

wrong answer 4th lines differ - expected: '319801028', found: '493591722'