NC200474. 会长的圣诞礼物
描述
输入描述
第一行输入一个整数M表示测试数据共有M(1<=M<=5)组
每组测试数据的第一行输入一个正整数N(1<=N<=100000)和一个正整数S(1<=S<=100000)，N表示红旗的总个数，S表示会长所在红旗处
随后的N-1行，每行有两个正整数a,b(1<=a,b<=N)，表示第a个红旗和第b个红旗之间有一条路连通。
输出描述
每组测试数据输N个正整数，其中，第i个数表示从S走到i个红旗，必须要经过的上一个红旗的编号。（其中i=S时，请输出-1）
示例1
输入:
1 10 1 1 9 1 8 8 10 10 3 8 6 1 2 10 4 9 5 3 7
输出:
-1 1 10 10 9 8 3 1 1 8
C(clang 3.9) 解法, 执行用时: 2ms, 内存消耗: 376K, 提交时间: 2019-12-21 14:18:56
#include <stdio.h>
int main()
{
int m,i;
scanf("%d",&m);
while(m--)
{
int a[100001],b,c;
int n,s;
scanf("%d%d",&n,&s);
for(i=1;i<n;i++)
{
scanf("%d",&c);
scanf("%d",&b);
a[b]=c;
}
for(i=1;i<=n;i++)
{
if(i==s)
{
printf("-1 ");
}
else
printf("%d ",a[i]);
}
}
return 0;
}
C++14(g++5.4) 解法, 执行用时: 7ms, 内存消耗: 400K, 提交时间: 2019-12-26 00:02:48
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int a[100005];
int t,n,s;
cin>>t;
while(t--) {
cin>>n>>s;
int x,y;
for(int i=1;i<n;i++) {
cin>>x>>y;
a[y]=x;
}
a[s]=-1;
for(int i=1;i<=n;i++) {
printf("%d ",a[i]);
}
cout<<endl;
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 3ms, 内存消耗: 336K, 提交时间: 2019-12-22 12:27:56
#include<bits/stdc++.h>
using namespace std;
int a[100005];
int main(){
int t,n,s;
cin>>t;
while(t--){
cin>>n>>s;
int x,y;
for(int i=1;i<n;i++){
cin>>x>>y;
a[y]=x;
}
a[s]=-1;
for(int i=1;i<=n;i++)
printf("%d ",a[i]);
}
return 0;
}