QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#166712#7103. Red Black TreezhoujiuAC ✓1216ms33708kbC++202.0kb2023-09-06 17:07:152023-09-06 17:07:16

Judging History

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

  • [2023-09-06 17:07:16]
  • 评测
  • 测评结果:AC
  • 用时:1216ms
  • 内存:33708kb
  • [2023-09-06 17:07:15]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=1e5+10;

int T,n,m,q;
vector<pair<int,int>> sons[N];
int cost[N],dist[N];
bool vis[N];
int fa[N][19],depth[N];

void bfs(int root)
{
	memset(depth,0x3f,sizeof(depth));
	depth[0]=0,depth[root]=1;

    queue<int> q;
    q.push(root);

    while(!q.empty())
    {
        int u=q.front();
        q.pop();

        for(auto [k,w]: sons[u])
        {
            if(depth[k]>depth[u]+1)
            {
                depth[k]=depth[u]+1;

                q.push(k);
                fa[k][0]=u;

                dist[k]=dist[u]+w;
                if(vis[k]) cost[k]=0;
                else cost[k]=cost[u]+w;

                for(int j=1;j<=18;j++)
                    fa[k][j]=fa[fa[k][j-1]][j-1];
            }
        }
    }
}

int lca(int a,int b)
{
	if(depth[a]<depth[b]) swap(a,b);

    for(int k=18;k>=0;k--)
    {
        if(depth[fa[a][k]]>=depth[b])
            a=fa[a][k];
    }

    if(a==b) return a;

    for(int k=18;k>=0;k--)
    {
        if(fa[a][k]!=fa[b][k])//防止越界
        {
            a=fa[a][k];
            b=fa[b][k];
        }
    }

    return fa[a][0];
}

void solve()
{
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++)
	{
		sons[i].clear();
		vis[i]=0;
	}

	for(int i=1;i<=m;i++)
	{
		int x;
		cin>>x;
		vis[x]=1;
	}

	for(int i=1;i<n;i++)
	{
		int a,b,w;
		cin>>a>>b>>w;

		sons[a].push_back({b,w});
		sons[b].push_back({a,w});
	}
	
	bfs(1);

	while(q--)
	{
		int t;
		cin>>t;

		vector<int> a; while(t--){ int x; cin>>x; a.push_back(x); } a.push_back(1);

		sort(a.begin(),a.end(),[&](int a,int b){
			return cost[a]>cost[b];
		});

		int ans=cost[a[1]],anc=a[0];
		t=dist[a[0]];

		for(int i=1;i<a.size()-1;i++)
		{
			anc=lca(anc,a[i]);
			t=max(t,dist[a[i]]);
			ans=min(ans,max(cost[a[i+1]],t-dist[anc]));
		}

		cout<<ans<<'\n';
	}
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin>>T;

	while(T--)
		solve();

	return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 10904kb

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: 1216ms
memory: 33708kb

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