QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#164125#7103. Red Black TreeLiberty12619AC ✓507ms29436kbC++202.3kb2023-09-04 20:07:182023-09-04 20:07:18

Judging History

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

  • [2023-09-04 20:07:18]
  • 评测
  • 测评结果:AC
  • 用时:507ms
  • 内存:29436kb
  • [2023-09-04 20:07:18]
  • 提交

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;
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;
        priority_queue<int>heap;
        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];});
        //for(int i=0;i<nums.size();i++)  cout<<i+1<<" "<<dist[nums[i]]<<endl;
        int ans=0,last = nums[0];
        if(nums.size()>1)   ans=d[nums[1]];
        heap.push(dist[nums[0]]);
        for(int i=1;i<nums.size();i++)
        {
            last = lca(last,nums[i]);
            heap.push(dist[nums[i]]);
            int t = heap.top();
            //cout<<i<<" "<<last<<endl;
            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;
	while(T--)
	{
        solve();
	}
	return 0;
}

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

详细

Test #1:

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

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: 507ms
memory: 29436kb

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