結果
問題 | No.812 Change of Class |
ユーザー | hide1214 |
提出日時 | 2019-04-12 22:37:47 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 625 ms / 4,000 ms |
コード長 | 2,461 bytes |
コンパイル時間 | 1,338 ms |
コンパイル使用メモリ | 115,920 KB |
実行使用メモリ | 13,824 KB |
最終ジャッジ日時 | 2023-09-03 13:37:30 |
合計ジャッジ時間 | 14,105 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 88 ms
9,460 KB |
testcase_01 | AC | 15 ms
4,376 KB |
testcase_02 | AC | 49 ms
6,692 KB |
testcase_03 | AC | 104 ms
10,452 KB |
testcase_04 | AC | 92 ms
9,652 KB |
testcase_05 | AC | 495 ms
11,732 KB |
testcase_06 | AC | 408 ms
11,148 KB |
testcase_07 | AC | 4 ms
4,424 KB |
testcase_08 | AC | 3 ms
4,380 KB |
testcase_09 | AC | 471 ms
11,992 KB |
testcase_10 | AC | 451 ms
11,984 KB |
testcase_11 | AC | 14 ms
7,012 KB |
testcase_12 | AC | 277 ms
10,388 KB |
testcase_13 | AC | 2 ms
4,380 KB |
testcase_14 | AC | 2 ms
4,376 KB |
testcase_15 | AC | 324 ms
9,152 KB |
testcase_16 | AC | 18 ms
4,380 KB |
testcase_17 | AC | 288 ms
9,464 KB |
testcase_18 | AC | 210 ms
7,584 KB |
testcase_19 | AC | 262 ms
8,408 KB |
testcase_20 | AC | 625 ms
11,656 KB |
testcase_21 | AC | 207 ms
7,372 KB |
testcase_22 | AC | 86 ms
5,176 KB |
testcase_23 | AC | 14 ms
4,380 KB |
testcase_24 | AC | 23 ms
4,384 KB |
testcase_25 | AC | 68 ms
4,884 KB |
testcase_26 | AC | 423 ms
10,400 KB |
testcase_27 | AC | 354 ms
9,608 KB |
testcase_28 | AC | 231 ms
8,468 KB |
testcase_29 | AC | 52 ms
4,376 KB |
testcase_30 | AC | 296 ms
9,340 KB |
testcase_31 | AC | 288 ms
8,204 KB |
testcase_32 | AC | 107 ms
5,736 KB |
testcase_33 | AC | 332 ms
9,980 KB |
testcase_34 | AC | 20 ms
4,376 KB |
testcase_35 | AC | 52 ms
4,592 KB |
testcase_36 | AC | 25 ms
4,384 KB |
testcase_37 | AC | 148 ms
5,828 KB |
testcase_38 | AC | 6 ms
4,776 KB |
testcase_39 | AC | 155 ms
6,056 KB |
testcase_40 | AC | 34 ms
4,384 KB |
testcase_41 | AC | 5 ms
4,564 KB |
testcase_42 | AC | 403 ms
8,464 KB |
testcase_43 | AC | 34 ms
6,672 KB |
testcase_44 | AC | 250 ms
7,064 KB |
testcase_45 | AC | 26 ms
4,380 KB |
testcase_46 | AC | 27 ms
6,648 KB |
testcase_47 | AC | 238 ms
7,136 KB |
testcase_48 | AC | 238 ms
7,984 KB |
testcase_49 | AC | 69 ms
4,444 KB |
testcase_50 | AC | 5 ms
4,380 KB |
testcase_51 | AC | 55 ms
4,876 KB |
testcase_52 | AC | 116 ms
7,092 KB |
testcase_53 | AC | 43 ms
4,376 KB |
testcase_54 | AC | 39 ms
4,380 KB |
testcase_55 | AC | 278 ms
10,428 KB |
testcase_56 | AC | 351 ms
12,376 KB |
testcase_57 | AC | 368 ms
12,972 KB |
testcase_58 | AC | 183 ms
8,060 KB |
testcase_59 | AC | 416 ms
13,824 KB |
testcase_60 | AC | 1 ms
4,380 KB |
testcase_61 | AC | 2 ms
4,388 KB |
testcase_62 | AC | 1 ms
4,380 KB |
ソースコード
#include<iostream> #include<vector> #include<string> #include<cmath> #include<algorithm> #include<functional> #include<numeric> #include<queue> #include<stack> #include<map> #include<unordered_map> #include<set> #include<bitset> #include<random> #pragma region using namespace std; #define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++) #define rep(i,n) FOR(i,0LL,n) #define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--) #define rrep(i,n) RFOR(i,0LL,n) #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define COUNT(a,y,x) upper_bound(all(a), y) - lower_bound(all(a), x) #define UNIQUE(a) sort(all(a)); a.erase(unique(all(a)), a.end()) #define pb push_back typedef long long int ll; typedef vector<ll> vll; typedef vector<vll> vvll; typedef pair<ll, ll> pll; typedef vector<pll> vpll; typedef vector<string> vs; typedef map<ll, ll> MAP; const ll inf = 2222222222222222222LL; const ll mod = 1000000007LL; ll n = 0, m = 0, ans = 0, tmp = 0, ma = -inf, mi = inf; string s; bool ok; ll dx[9] = { 0,1,-1,0,0,1,1,-1,-1 }, dy[9] = { 0,0,0,1,-1,1,-1,1,-1 }; #define endl '\n' #pragma endregion #define MAX 222222 struct Weighted_Graph { struct edge { ll node, cost; }; vector<vector<edge>> e; Weighted_Graph(ll x = MAX) { e.resize(x + 1); } void add_edge(ll a, ll b, ll c) { e[a].pb(edge{ b,c }); } vll dijkstra(ll start) { priority_queue<pll, vector<pll>, greater<pll>> pq; ll u; pll p; vll dist(e.size(), inf); dist[start] = 0; pq.push(pll(0, start)); while (!pq.empty()) { p = pq.top(); pq.pop(); u = p.second; if (dist[u] < p.first) continue; for (edge e1 : e[u]) { if (dist[e1.node] > dist[u] + e1.cost) { dist[e1.node] = dist[u] + e1.cost; pq.push(pll(dist[e1.node], e1.node)); } } } return dist; } }; int main(void) { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; Weighted_Graph wg(n); rep(i, m) { ll a, b; cin >> a >> b; wg.add_edge(a, b, 1); wg.add_edge(b, a, 1); } cin >> m; rep(i, m) { ll a; cin >> a; vll v = wg.dijkstra(a); ans = 0; ma = 0; FOR(j, 1, n + 1) { if (v[j] > inf / 2) continue; ma = max(ma, v[j]); ans++; } if (ma == 1) ma = 0; FOR(i, 1, 100) { if (!ma) break; if (powl(2, i) >= ma) { ma = i; break; } } cout << ans - 1 << " " << ma << endl; } return 0; }