結果

問題 No.277 根掘り葉掘り
ユーザー IL_mstaIL_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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0