結果
問題 | No.812 Change of Class |
ユーザー |
![]() |
提出日時 | 2019-04-12 22:19:43 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 163 ms / 4,000 ms |
コード長 | 5,001 bytes |
コンパイル時間 | 1,094 ms |
コンパイル使用メモリ | 124,316 KB |
実行使用メモリ | 12,148 KB |
最終ジャッジ日時 | 2024-06-12 19:00:26 |
合計ジャッジ時間 | 6,129 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 60 |
ソースコード
// includes {{{ #include<iostream> #include<iomanip> #include<algorithm> #include<vector> #include<stack> #include<queue> #include<map> #include<set> #include<tuple> #include<cmath> #include<random> #include<cassert> #include<cstring> // #include<deque> // #include<multiset> // #include<bitset> // #include<cstring> // #include<bits/stdc++.h> // }}} using namespace std; using ll = long long; // #undef DEBUG // #define DEBUG // DEBUG {{{ #include <array> #include <deque> #include <list> #include <ostream> #include <queue> #include <stack> #include <tuple> #include <valarray> #include <vector> template < int n, class... T > typename std::enable_if< (n >= sizeof...(T)) >::type __output_tuple( std::ostream &, std::tuple< T... > const &) {} template < int n, class... T > typename std::enable_if< (n < sizeof...(T)) >::type __output_tuple( std::ostream &os, std::tuple< T... > const &t) { os << (n == 0 ? "" : ", ") << std::get< n >(t); __output_tuple< n + 1 >(os, t); } template < class... T > std::ostream &operator<<(std::ostream &os, std::tuple< T... > const &t) { os << "("; __output_tuple< 0 >(os, t); os << ")"; return os; } template < class T, class U > std::ostream &operator<<(std::ostream &os, std::pair< T, U > const &p) { os << "(" << p.first << ", " << p.second << ")"; return os; } template < class T > std::ostream &operator<<(std::ostream &os, const std::stack< T > &a) { os << "{"; for(auto tmp = a; tmp.size(); tmp.pop()) os << (a.size() == tmp.size() ? "" : ", ") << tmp.top(); os << "}"; return os; } template < class T, class Container, class Compare > std::ostream &operator<<(std::ostream &os, std::priority_queue< T, Container, Compare > a) { os << "{ (top) "; while(a.size()) os << a.top() << (a.size() == 1 ? "" : ", "), a.pop(); os << " }"; return os; } template < class T, class Container > std::ostream &operator<<(std::ostream &os, std::queue< T, Container > a) { os << "{ "; while(a.size()) os << a.front() << (a.size() == 1 ? "" : ", "), a.pop(); os << " }"; return os; } #ifdef DEBUG #if !defined(DEBUG_OUT) #define DEBUG_OUT std::cerr #endif #define dump(...) \ [&]() { \ auto __debug_tap = std::make_tuple(__VA_ARGS__); \ DEBUG_OUT << "[" << __LINE__ << "] " << #__VA_ARGS__ << " = " << __debug_tap \ << std::endl; \ }() template < class T > inline void dump2D(T &d, size_t sizey, size_t sizex) { for(size_t i = 0; i < sizey; i++) { DEBUG_OUT << "\t"; for(size_t j = 0; j < sizex; j++) DEBUG_OUT << d[i][j] << (j + 1 == sizex ? "" : "\t"); DEBUG_OUT << std::endl; } } template < class T > inline void dump1D(T &d, size_t sizey) { for(size_t i = 0; i < sizey; i++) { DEBUG_OUT << d[i] << (i + 1 == sizey ? "" : " "); } DEBUG_OUT << std::endl; } template < class T, class = typename std::iterator_traits< decltype(begin(T())) >::value_type, class = typename std::enable_if< !std::is_same< T, std::string >::value >::type > std::ostream &operator<<(std::ostream &os, const T &a) { os << "{"; for(auto ite = begin(a); ite != end(a); ++ite) os << (ite == begin(a) ? "" : ", ") << *ite; os << "}"; return os; } #else #define dump(...) (42) #define dump2D(...) (42) #define dump1D(...) (42) template < class T, class = typename std::iterator_traits< decltype(begin(T())) >::value_type, class = typename std::enable_if< !std::is_same< T, std::string >::value >::type > std::ostream &operator<<(std::ostream &os, const T &a) { for(auto ite = begin(a); ite != end(a); ++ite) os << (ite == begin(a) ? "" : " ") << *ite; return os; } #endif // }}} int lg(int x) { int n = 0, t = 1; while(t < x) t <<= 1, n++; return n; } const int N = 1e5; std::vector<std::vector<int>> g; int n, m; int dist[N][3]; void bfs(int f, int i, vector<int> & v) { queue<pair<int, int>> q; q.emplace(i, 0); dist[i][f] = 0; while(q.size()) { int i, d; tie(i, d) = q.front(); dist[i][f] = d; v.emplace_back(i); q.pop(); for(auto j : g[i]) { if(dist[j][f] == -1) { dist[j][f] = d + 1; q.emplace(j, d + 1); } } } } int main() { std::ios::sync_with_stdio(false), std::cin.tie(0); cin >> n >> m; g.resize(n); for(int i = 0; i < m; i++) { int a, b; std::cin >> a >> b; a--; b--; g[a].emplace_back(b); g[b].emplace_back(a); } vector<int> ans1(n); vector<int> ans2(n); int q; cin >> q; while(q--) { memset(dist, -1, sizeof dist); int a; cin >> a; a--; vector<int> v; bfs(0, a, v); ans1[a] = v.size()-1; for(auto e : v) { ans2[a] = max(lg(dist[e][0]), ans2[a]); } cout << ans1[a] << " " << ans2[a] << "\n"; } return 0; }