QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#377185#7103. Red Black TreeLiberty12619AC ✓508ms30088kbC++202.3kb2024-04-05 00:40:272024-04-05 00:40:28

Judging History

This is the latest submission verdict.

  • [2024-04-05 00:40:28]
  • Judged
  • Verdict: AC
  • Time: 508ms
  • Memory: 30088kb
  • [2024-04-05 00:40:27]
  • Submitted

answer

#include<bits/stdc++.h>
#define x first
#define y second
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N=1e5+10,M=N*2,INF = 1e15,mod = 998244353;
bool red[N];
int h[N],e[M],ne[M],w[M],idx,d[N];
int dfn[N],dist[N],st[20][N],times;
int lg[N];
void init()
{
    for(int t=1,res=-1,i=1;i<N;i++)
    {
        if(i==t)
        {
            t*=2;
            res++;
        }
        lg[i]=res;
    }
}
void add(int a,int b,int c)
{
    e[idx] = b, w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u,int fa,int sum)
{
    if(red[u])  sum=0;
    st[0][dfn[u]=++times]=fa,d[u]=sum;
    for(int i = h[u];~i;i=ne[i])
    {
        int j = e[i];
        if(j==fa)   continue;
        dist[j]=dist[u]+w[i];
        dfs(j,u,sum+w[i]);
    }
}
int get(int u,int v)
{
    return dfn[u]<dfn[v]?u:v;
}
int lca(int u,int v)
{
    if(u==v)    return u;
    if(dfn[u]>dfn[v])   swap(u,v);
    u=dfn[u],v=dfn[v];
    int d = lg[v-u++];
    return get(st[d][u],st[d][v-(1<<d)+1]);
}
void solve()
{
    int n,m,q;
    times=idx=0;
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)h[i]=-1,red[i]=false;
    for(int i=1;i<=m;i++)
    {
        int x;
        cin>>x;
        red[x]=true;
    }
    for(int i=1;i<n;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w),add(v,u,w);
    }
    dfs(1,0,0);
    for(int i=1;i<=lg[n];i++)
        for(int j=1;j+(1<<i)-1<=n;j++)
            st[i][j]=get(st[i-1][j],st[i-1][j+(1<<i-1)]);
    while(q--)
    {
        int k;
        cin>>k;
        vector<int>nums;
        for(int i=1;i<=k;i++)
        {
            int x;
            cin>>x;
            nums.push_back(x);
        }
        sort(nums.begin(),nums.end(),[&](int a,int b){return d[a]>d[b];});
        int ans=0,last = nums[0];
        if(nums.size()>1)   ans=d[nums[1]];
        int t=dist[nums[0]];
        for(int i=1;i<nums.size();i++)
        {
            last = lca(last,nums[i]);
            t = max(t,dist[nums[i]]);
            if(i+1<nums.size()) ans=min(ans,max(t-dist[last],d[nums[i+1]]));
            else    ans=min(ans,t-dist[last]);
        }
        cout<<ans<<"\n";
    }
}

signed main()
{
    int T=1;
    cin.tie(0)->sync_with_stdio(false);
    cin>>T;
    init();
    while(T--)
    {
        solve();
    }
    return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 14568kb

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: 508ms
memory: 30088kb

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