結果
問題 | No.812 Change of Class |
ユーザー | fiord |
提出日時 | 2019-04-13 13:07:33 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 183 ms / 4,000 ms |
コード長 | 3,636 bytes |
コンパイル時間 | 1,305 ms |
コンパイル使用メモリ | 128,128 KB |
実行使用メモリ | 9,320 KB |
最終ジャッジ日時 | 2023-09-03 14:48:16 |
合計ジャッジ時間 | 7,553 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 75 ms
8,504 KB |
testcase_01 | AC | 14 ms
6,164 KB |
testcase_02 | AC | 42 ms
7,220 KB |
testcase_03 | AC | 88 ms
8,952 KB |
testcase_04 | AC | 78 ms
8,604 KB |
testcase_05 | AC | 183 ms
8,656 KB |
testcase_06 | AC | 160 ms
8,112 KB |
testcase_07 | AC | 5 ms
5,840 KB |
testcase_08 | AC | 4 ms
5,712 KB |
testcase_09 | AC | 170 ms
8,936 KB |
testcase_10 | AC | 176 ms
8,952 KB |
testcase_11 | AC | 20 ms
6,856 KB |
testcase_12 | AC | 119 ms
8,628 KB |
testcase_13 | AC | 4 ms
5,696 KB |
testcase_14 | AC | 3 ms
5,696 KB |
testcase_15 | AC | 118 ms
7,756 KB |
testcase_16 | AC | 11 ms
5,864 KB |
testcase_17 | AC | 113 ms
8,216 KB |
testcase_18 | AC | 84 ms
7,320 KB |
testcase_19 | AC | 97 ms
7,644 KB |
testcase_20 | AC | 179 ms
8,872 KB |
testcase_21 | AC | 82 ms
7,272 KB |
testcase_22 | AC | 38 ms
6,444 KB |
testcase_23 | AC | 9 ms
5,920 KB |
testcase_24 | AC | 12 ms
5,948 KB |
testcase_25 | AC | 31 ms
6,284 KB |
testcase_26 | AC | 151 ms
8,620 KB |
testcase_27 | AC | 129 ms
8,060 KB |
testcase_28 | AC | 95 ms
7,720 KB |
testcase_29 | AC | 23 ms
6,108 KB |
testcase_30 | AC | 120 ms
7,872 KB |
testcase_31 | AC | 101 ms
7,516 KB |
testcase_32 | AC | 47 ms
6,704 KB |
testcase_33 | AC | 129 ms
8,212 KB |
testcase_34 | AC | 12 ms
5,980 KB |
testcase_35 | AC | 25 ms
6,276 KB |
testcase_36 | AC | 11 ms
6,040 KB |
testcase_37 | AC | 56 ms
6,852 KB |
testcase_38 | AC | 9 ms
6,096 KB |
testcase_39 | AC | 58 ms
6,980 KB |
testcase_40 | AC | 18 ms
6,048 KB |
testcase_41 | AC | 7 ms
6,012 KB |
testcase_42 | AC | 116 ms
7,936 KB |
testcase_43 | AC | 35 ms
7,228 KB |
testcase_44 | AC | 81 ms
7,340 KB |
testcase_45 | AC | 11 ms
5,908 KB |
testcase_46 | AC | 33 ms
7,240 KB |
testcase_47 | AC | 81 ms
7,356 KB |
testcase_48 | AC | 92 ms
7,692 KB |
testcase_49 | AC | 25 ms
6,380 KB |
testcase_50 | AC | 4 ms
5,720 KB |
testcase_51 | AC | 29 ms
6,428 KB |
testcase_52 | AC | 57 ms
7,324 KB |
testcase_53 | AC | 17 ms
6,084 KB |
testcase_54 | AC | 15 ms
6,052 KB |
testcase_55 | AC | 56 ms
8,172 KB |
testcase_56 | AC | 61 ms
8,812 KB |
testcase_57 | AC | 65 ms
8,912 KB |
testcase_58 | AC | 36 ms
7,320 KB |
testcase_59 | AC | 73 ms
9,320 KB |
testcase_60 | AC | 4 ms
5,696 KB |
testcase_61 | AC | 3 ms
5,808 KB |
testcase_62 | AC | 3 ms
5,816 KB |
ソースコード
#define _USE_MATH_DEFINES #include <iostream> #include <fstream> #include <cstdio> #include <cmath> #include <cstdlib> #include <cstring> #include <cassert> #include <string> #include <vector> #include <utility> #include <complex> #include <set> #include <map> #include <unordered_map> #include <queue> #include <stack> #include <deque> #include <tuple> #include <bitset> #include <limits> #include <algorithm> #include <array> #include <random> #include <complex> #include <regex> using namespace std; typedef long double ld; typedef long long ll; typedef vector<int> vint; typedef vector<ll> vll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<double, double> pdd; typedef complex<ld> compd; #define quickIO() {cin.tie(0); cout.sync_with_stdio(false);} #define reach(i,a) for(auto i:a) #define rep(i,n) for(int i=0;i<((int)n);i++) #define REP(i,n) for(int i=0;i<=((int)n);i++) #define srep(i,a,n) for(int i=a;i<((int)n);i++) #define SREP(i,a,n) for(int i=a;i<=((int)n);i++) #define rrep(i,n) for(int i=n-1;i>=0;i--) #define RREP(i,n) for(int i=n;i>=0;i--) #define all(a) (a).begin(),(a).end() #define mp(a,b) make_pair(a,b) #define mt make_tuple #define pb push_back template<typename T> istream& operator >> (istream& is, vector<T>& vec) { for (T& x : vec) is >> x; return is; } template<typename T> ostream& operator << (ostream& os, vector<T>& vec) { os << "["; rep(i, vec.size()) os << (i ? ", " : "") << vec[i]; os << "]"; return os; } template<typename T> istream& operator >> (istream& is, pair<T, T>& p) { is >> p.first >> p.second; return is; } template<typename T> ostream& operator << (ostream& os, pair<T, T>& p) { os << "(" << p.first << ", " << p.second << ")"; return os; } int bitcnt(ll x) { x = ((x & 0xAAAAAAAAAAAAAAAA) >> 1) + (x & 0x5555555555555555); x = ((x & 0xCCCCCCCCCCCCCCCC) >> 2) + (x & 0x3333333333333333); x = ((x & 0xF0F0F0F0F0F0F0F0) >> 4) + (x & 0x0F0F0F0F0F0F0F0F); x = ((x & 0xFF00FF00FF00FF00) >> 8) + (x & 0x00FF00FF00FF00FF); x = ((x & 0xFFFF0000FFFF0000) >> 16) + (x & 0x0000FFFF0000FFFF); x = ((x & 0xFFFFFFFF00000000) >> 32) + (x & 0x00000000FFFFFFFF); return x; } int bitcnt(int x) { x = ((x & 0xAAAAAAAA) >> 1) + (x & 0x55555555); x = ((x & 0xCCCCCCCC) >> 2) + (x & 0x33333333); x = ((x & 0xF0F0F0F0) >> 4) + (x & 0x0F0F0F0F); x = ((x & 0xFF00FF00) >> 8) + (x & 0x00FF00FF); x = ((x & 0xFFFF0000) >> 16) + (x & 0x0000FFFF); return x; } ll sqrtll(ll x) { ll left = 0, right = x; rep(i, 100) { ll mid = (left + right) >> 1; if (mid*mid <= x) left = mid; else right = mid; } return left; } ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a%b); } #define debug(x) printf("Case #%d: ", x) #define DEBUG 0 const ll inf = 1e9; const ld infl = 1e100; const ll mod = 1e9 + 7; const ld eps = 1e-9; const int dx[] = { 1,0,-1,0,0 }; const int dy[] = { 0,1,0,-1,0 }; vint edge[100010]; int depth[100010]; int main() { int n, m; cin >> n >> m; rep(i, m) { int p, q; cin >> p >> q; p--; q--; edge[p].push_back(q); edge[q].push_back(p); } int q; cin >> q; rep(i, q) { int a; cin >> a; a--; // BFS rep(j, n) depth[j] = inf; depth[a] = 0; queue<int> que; que.push(a); while (!que.empty()) { int pos = que.front(); que.pop(); rep(j, edge[pos].size()) { int to = edge[pos][j]; if (depth[to] > depth[pos] + 1) { depth[to] = depth[pos] + 1; que.push(to); } } } int cnt = -1; int path = 0; rep(j, n) { if (depth[j] < inf) { cnt++; path = max(path, depth[j]); } } int day = 0; if (cnt > 0) while (path > (1 << day)) day++; cout << cnt << " " << day << endl; } return 0; }