CODE FESTIVAL 2016 Relay (Parallel)

Submission #1356213

Source codeソースコード

#include<bits/stdc++.h>
using namespace std;
int n,a,b,cnt,dist[110000];vector<int>x[110000];bool used[110000];
void dfs(int pos,int depth){
	if(used[pos]==true)return;
	used[pos]=true;dist[pos]=depth;
	for(int i=0;i<x[pos].size();i++)dfs(x[pos][i],depth+(x[pos].size()==2));
}
int main(){
	cin>>n;for(int i=1;i<=n-1;i++){cin>>a>>b;x[a].push_back(b);x[b].push_back(a);}
	for(int i=1;i<=n;i++){if(x[i].size()==1)cnt++;}
	for(int i=1;i<=n;i++)used[i]=false;dfs(1,0);
	int maxn=0,maxid=0;for(int i=1;i<=n;i++){if(maxn<dist[i]){maxn=dist[i];maxid=i;}}
	for(int i=1;i<=n;i++)used[i]=false;dfs(maxid,0);
	sort(dist+1,dist+n+1);
	cout<<cnt+dist[n]<<endl;
	return 0;
}

Submission

Task問題 K - 木の問題 / Problem on Tree
User nameユーザ名 E869120
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 679 Byte
File nameファイル名
Exec time実行時間 105 ms
Memory usageメモリ使用量 6528 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_01.txt,sample_02.txt
All 100 / 100 sample_01.txt,sample_02.txt,sample_01.txt,sample_02.txt,subtask1_01.txt,subtask1_02.txt,subtask1_03.txt,subtask1_04.txt,subtask1_05.txt,subtask1_06.txt,subtask1_07.txt,subtask1_08.txt,subtask1_09.txt,subtask1_10.txt,subtask1_11.txt,subtask1_12.txt,subtask1_13.txt,subtask1_14.txt,subtask1_15.txt,subtask1_16.txt,subtask1_17.txt,subtask1_18.txt,subtask1_19.txt,subtask1_20.txt,subtask1_21.txt,subtask1_22.txt,subtask1_23.txt,subtask1_24.txt,subtask1_25.txt,subtask1_26.txt,subtask1_27.txt,subtask1_28.txt,subtask1_29.txt,subtask1_30.txt,subtask1_31.txt,subtask1_32.txt,subtask1_33.txt,subtask1_34.txt,subtask1_35.txt,subtask1_36.txt,subtask1_37.txt,subtask1_38.txt,subtask1_39.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample_01.txt AC 2 ms 2816 KB
sample_02.txt AC 2 ms 2816 KB
subtask1_01.txt AC 84 ms 5888 KB
subtask1_02.txt AC 67 ms 5248 KB
subtask1_03.txt AC 28 ms 3840 KB
subtask1_04.txt AC 36 ms 4096 KB
subtask1_05.txt AC 43 ms 4352 KB
subtask1_06.txt AC 6 ms 2944 KB
subtask1_07.txt AC 101 ms 6400 KB
subtask1_08.txt AC 27 ms 3840 KB
subtask1_09.txt AC 62 ms 5120 KB
subtask1_10.txt AC 79 ms 5760 KB
subtask1_11.txt AC 37 ms 4224 KB
subtask1_12.txt AC 14 ms 3328 KB
subtask1_13.txt AC 9 ms 3072 KB
subtask1_14.txt AC 9 ms 3072 KB
subtask1_15.txt AC 103 ms 6528 KB
subtask1_16.txt AC 103 ms 6528 KB
subtask1_17.txt AC 102 ms 6528 KB
subtask1_18.txt AC 101 ms 6528 KB
subtask1_19.txt AC 102 ms 6528 KB
subtask1_20.txt AC 101 ms 6528 KB
subtask1_21.txt AC 103 ms 6528 KB
subtask1_22.txt AC 101 ms 6528 KB
subtask1_23.txt AC 102 ms 6528 KB
subtask1_24.txt AC 104 ms 6528 KB
subtask1_25.txt AC 102 ms 6528 KB
subtask1_26.txt AC 102 ms 6528 KB
subtask1_27.txt AC 103 ms 6528 KB
subtask1_28.txt AC 101 ms 6528 KB
subtask1_29.txt AC 103 ms 6528 KB
subtask1_30.txt AC 101 ms 6528 KB
subtask1_31.txt AC 102 ms 6528 KB
subtask1_32.txt AC 101 ms 6528 KB
subtask1_33.txt AC 102 ms 6528 KB
subtask1_34.txt AC 101 ms 6528 KB
subtask1_35.txt AC 105 ms 6528 KB
subtask1_36.txt AC 102 ms 6528 KB
subtask1_37.txt AC 102 ms 6528 KB
subtask1_38.txt AC 101 ms 6528 KB
subtask1_39.txt AC 103 ms 6528 KB