結果

問題 No.277 根掘り葉掘り
ユーザー IL_mstaIL_msta
提出日時 2015-09-05 07:45:40
言語 C++11
(gcc 8.5.0)
結果
AC  
実行時間 183 ms / 3,000 ms
コード長 1,987 bytes
コンパイル時間 1,001 ms
使用メモリ 11,516 KB
最終ジャッジ日時 2023-02-17 05:58:40
合計ジャッジ時間 4,386 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
testcase_00 AC 1 ms
9,756 KB
testcase_01 AC 1 ms
7,572 KB
testcase_02 AC 1 ms
7,612 KB
testcase_03 AC 1 ms
7,672 KB
testcase_04 AC 1 ms
7,660 KB
testcase_05 AC 1 ms
9,680 KB
testcase_06 AC 1 ms
7,680 KB
testcase_07 AC 1 ms
9,680 KB
testcase_08 AC 1 ms
9,712 KB
testcase_09 AC 183 ms
9,688 KB
testcase_10 AC 161 ms
10,932 KB
testcase_11 AC 171 ms
11,516 KB
testcase_12 AC 164 ms
10,496 KB
testcase_13 AC 180 ms
10,620 KB
testcase_14 AC 169 ms
10,516 KB
testcase_15 AC 169 ms
10,252 KB
testcase_16 AC 166 ms
10,420 KB
testcase_17 AC 170 ms
10,476 KB
testcase_18 AC 165 ms
10,264 KB
testcase_19 AC 168 ms
10,540 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void addEdge(int, int)’:
main.cpp:41:25: warning: narrowing conversion of ‘(& g.std::vector<std::vector<Edge> >::operator[](((std::vector<std::vector<Edge> >::size_type)t)))->std::vector<Edge>::size()’ from ‘std::vector<Edge>::size_type’ {aka ‘long unsigned int’} to ‘int’ inside { } [-Wnarrowing]
  Edge a = { t, g[t].size() };
                ~~~~~~~~~^~
main.cpp:42:25: warning: narrowing conversion of ‘(& g.std::vector<std::vector<Edge> >::operator[](((std::vector<std::vector<Edge> >::size_type)s)))->std::vector<Edge>::size()’ from ‘std::vector<Edge>::size_type’ {aka ‘long unsigned int’} to ‘int’ inside { } [-Wnarrowing]
  Edge b = { s, g[s].size() };
                ~~~~~~~~~^~

ソースコード

diff # 

#define _USE_MATH_DEFINES
 
#include <iostream>
#include <iomanip>
#include <sstream>
 
#include <algorithm>
#include <cmath>
 
#include <string>
//#include <array>
#include <list>
#include <queue>
#include <vector>
#include <complex>
#include <set>
#include <map>
 
/////////
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define P(p) cout<<(p)<<endl;
 
#define PII pair<int,int>
/////////
typedef long long LL;
typedef long double LD;
/////////
using namespace::std;
/////////
vector<bool> use;
vector<int> ne;
vector<int> ha;

struct Edge{
	int to, rev;
};
vector<vector<Edge>> g;

void addEdge(int s,int t){
	Edge a = { t, g[t].size() };
	Edge b = { s, g[s].size() };
	g[s].push_back( a );
	g[t].push_back( b );
}

int main(void){
    std::cin.tie(0); 
    std::ios::sync_with_stdio(false);
    std::cout << std::fixed;//
    //cout << setprecision(16);//
	
	int N;
	cin >> N;
	
	g.resize(N);
	use.resize(N);
	ne.resize(N);
	ha.resize(N);
	int posA,posB;
	rep(i,N-1){
		cin >> posA >> posB;
		addEdge(posA-1,posB-1);
	}
	rep(i,N){
		use[i] = false;
		ne[i] = -1;
		ha[i] = -1;
	}
	
	queue<PII> q;
	use[0] = true;
	ne[0] = 0;
	q.push( PII( 0, ne[0] ) );

	PII temp;
	vector<Edge>::iterator it,end;
	while( !q.empty() ){
		temp = q.front();
		q.pop();
		it = g[temp.first].begin();
		end = g[temp.first].end();
		while( it != end ){
			if( !use[it->to] ){
				use[it->to] = true;
				ne[it->to] = temp.second + 1;
				q.push( PII(it->to,temp.second+1) );
			}
			++it;
		}
	}
	rep(i,N){
		use[i] = false;
	}
	for(int i=1;i<N; ++i){
		if( g[i].size() == 1 ){
			use[i] = true;
			ha[i] = 0;
			q.push( PII( i, 0) );
		}
	}

	while( !q.empty() ){
		temp = q.front();
		q.pop();
		it = g[temp.first].begin();
		end = g[temp.first].end();
		while( it != end ){
			if( !use[it->to] ){
				use[it->to] = true;
				ha[it->to] = temp.second + 1;
				q.push( PII(it->to,temp.second+1) );
			}
			++it;
		}
	}
	rep(i,N){
		P( min( ne[i], ha[i] ) );
	}
	return 0;
}
0