列表

详情

NC24624. [USACO 2011 Mar S]Meeting Place

描述

Bessie and Jonell are great friends. Since Farmer John scrambles where the cows graze every day, they are sometimes quite far from each other and can't talk.
The pastures and paths on FJ's farm form a 'tree' structure. Each pasture has exactly one distinct path to any other pasture, and each pasture (except pasture #1, the 'root') also has a single parent node.
Bessie and Jonell have decided that they will always meet at the closest pasture that that is both an ancestor of Jonell's pasture and of Bessie's pasture.
FJ created a map of his N (1 <= N <= 1,000) pastures (conveniently numbered 1..N) that tells the parent P_i (1 <= P_i <= N) of each pasture except pasture 1, which has no parent.
FJ has released his daily grazing schedule for the next M (1 <= M <= 1,000) days, so Bessie and Jonell are deciding where they should meet each day for gossip. On day k, Bessie is in pasture B_k (1 <= B_k <= N) and Jonell is in pasture J_k (1 <= J_k <= N).

Given a map and schedule, help Bessie and Jonell find their meeting places.

输入描述

* Line 1: Two space-separated integers: N and M
* Lines 2..N: Line i contains a single integer that describes the parent of pasture i: P_i
* Lines N+1..N+M: Line k+N describes Bessie and Jonell's respective pastures with two space-separated integers: B_k and J_k

输出描述

* Lines 1..M: Line j contains the meeting place Bessie and Jonell would use for line j+N of the input

示例1

输入: 

9 6 
1 
1 
2 
8 
1 
8 
6 
6 
2 7 
4 2 
3 3 
4 1 
7 5 
9 5

输出: 

1
2
3
1
8
6

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 7ms, 内存消耗: 364K, 提交时间: 2020-01-11 08:31:02 

#include<iostream>
#include<cstdio>
using namespace std;
int n,K,m,fa[101010];
int dep[101010];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=2;i<=n;i++)
	scanf("%d",&fa[i]);
	for(int i=1;i<=n;i++)
	{
		int x=i,dp=0;
		while(fa[x]) dp++,x=fa[x];
		dep[i]=dp+1;
	}
	while(m--)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		if(dep[x]<dep[y]) swap(x,y);
		while(dep[x]>dep[y]) x=fa[x];
		while(x!=y) x=fa[x],y=fa[y];
		printf("%d\n",x);
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 6ms, 内存消耗: 372K, 提交时间: 2020-01-12 11:49:01 

#include<stdio.h>
#include<string.h>
int fa[1005],used[1005];
void find1(int x){
	used[x]=1;
	if(x!=1)	find1(fa[x]);
}
int find2(int x){
	if(used[x]==1)	return x;
	else find2(fa[x]);
}
int main(){
	int n,m,i,p,x,y;
	scanf("%d%d",&n,&m);
	fa[1]=1;
	for(i=2;i<=n;i++){
		scanf("%d",&p);
		fa[i]=p;
	}
	while(m--){
		memset(used,0,sizeof(used));
		scanf("%d%d",&x,&y);
		find1(x);
		printf("%d\n",find2(y));
	}
}

上一题

© 2024 nowcoder.com