結果

問題 No.277 根掘り葉掘り
ユーザー IL_msta
提出日時 2015-09-05 07:45:40
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 187 ms / 3,000 ms
コード長 1,987 bytes
コンパイル時間 1,031 ms
コンパイル使用メモリ 104,024 KB
実行使用メモリ 11,392 KB
最終ジャッジ日時 2024-07-19 03:45:15
合計ジャッジ時間 4,049 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void addEdge(int, int)’:
main.cpp:41:32: 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’ [-Wnarrowing]
   41 |         Edge a = { t, g[t].size() };
      |                       ~~~~~~~~~^~
main.cpp:42:32: 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’ [-Wnarrowing]
   42 |         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