QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#377176#7103. Red Black TreeLiberty12619WA 0ms14056kbC++202.2kb2024-04-05 00:26:372024-04-05 00:26:38

Judging History

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

  • [2024-04-05 00:26:38]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:14056kb
  • [2024-04-05 00:26:37]
  • 提交

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]=u,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];});
        int ans=d[nums[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();
            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;
}

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 14056kb

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:

0
3
0
0
0
0
0

result:

wrong answer 1st lines differ - expected: '4', found: '0'