QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#156724#7103. Red Black Treeucup-team1321#AC ✓1510ms25528kbC++232.5kb2023-09-02 14:07:362023-09-02 14:52:10

Judging History

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

  • [2023-09-02 14:52:10]
  • 评测
  • 测评结果:AC
  • 用时:1510ms
  • 内存:25528kb
  • [2023-09-02 14:07:36]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=100005;
int n,m,q;
int r[N];
int c[N];
vector<pair<int,int>>G[N];
long long dis[N];
int pre[N];
int mi[20][N];
int dfn[N],Index;
int lg2[N];
void init(int n=100000)
{
    lg2[0]=-1;
    for(int i=1;i<=n;i++)
        lg2[i]=lg2[i/2]+1;
    return;
}
int dmin(int x,int y){return dfn[x]<dfn[y]?x:y;}
void dfs(int u,int father)
{
    if(c[u]) pre[u]=u;
    else pre[u]=pre[father];
    dfn[u]=++Index;
    mi[0][dfn[u]]=father;
    for(auto [v,w]:G[u])
    {
        if(v==father) continue;
        dis[v]=dis[u]+w;
        dfs(v,u);
    }
    return;
}
int lca(int u,int v)
{
    if(u==v) return u;
    u=dfn[u],v=dfn[v];
    if(u>v) swap(u,v);
    int d=lg2[v-u];
    return dmin(mi[d][u+1],mi[d][v-(1<<d)+1]);
}
int p[N],k;
void solve()
{
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=m;i++)
        scanf("%d",&r[i]);
    for(int i=1;i<=n;i++)
        G[i].clear();
    long long sum=0;
    for(int i=1;i<n;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        G[x].emplace_back(y,z);
        G[y].emplace_back(x,z);
        sum+=z;
    }
    for(int i=1;i<=n;i++)
        c[i]=0;
    for(int i=1;i<=m;i++)
        c[r[i]]=1;
    dis[1]=0;
    Index=0;
    dfs(1,0);
    for(int i=1;(1<<i)<=n;i++)
        for(int j=1;j+(1<<i)-1<=n;j++)
            mi[i][j]=dmin(mi[i-1][j],mi[i-1][j+(1<<(i-1))]);
    while(q--)
    {
        scanf("%d",&k);
        for(int i=1;i<=k;i++)
            scanf("%d",&p[i]);
        auto check=[=](long long x)
        {
            vector<int>pos;
            for(int i=1;i<=k;i++)
                if(dis[p[i]]-dis[pre[p[i]]]>x) pos.emplace_back(p[i]);
            if(pos.empty()) return true;
            int l=pos[0];
            for(int i=1;i<(int)pos.size();i++)
                l=lca(l,pos[i]);
            for(int u:pos)
                if(dis[u]-dis[l]>x) return false;
            return true;
        };
        long long l=0,r=sum,ans=0;
        while(l<=r)
        {
            long long mid=(l+r)/2;
            if(check(mid)) ans=mid,r=mid-1;
            else l=mid+1;
        }
        printf("%lld\n",ans);
    }
    return;
}
int main()
{
    init();
    int T;
    scanf("%d",&T);
    while(T--)
        solve();
    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
*/

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

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 10328kb

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: 1510ms
memory: 25528kb

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