結果
問題 | No.1254 補強への架け橋 |
ユーザー | micheeeeell1001 |
提出日時 | 2020-10-09 23:17:56 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 179 ms / 2,000 ms |
コード長 | 3,865 bytes |
コンパイル時間 | 2,430 ms |
コンパイル使用メモリ | 218,528 KB |
実行使用メモリ | 33,808 KB |
最終ジャッジ日時 | 2023-09-27 19:42:28 |
合計ジャッジ時間 | 13,762 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 2 ms
4,376 KB |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | AC | 1 ms
4,380 KB |
testcase_06 | AC | 1 ms
4,376 KB |
testcase_07 | AC | 1 ms
4,376 KB |
testcase_08 | AC | 1 ms
4,380 KB |
testcase_09 | AC | 2 ms
4,376 KB |
testcase_10 | AC | 2 ms
4,376 KB |
testcase_11 | AC | 1 ms
4,380 KB |
testcase_12 | AC | 2 ms
4,380 KB |
testcase_13 | AC | 2 ms
4,376 KB |
testcase_14 | AC | 2 ms
4,380 KB |
testcase_15 | AC | 1 ms
4,380 KB |
testcase_16 | AC | 2 ms
4,376 KB |
testcase_17 | AC | 2 ms
4,376 KB |
testcase_18 | AC | 1 ms
4,376 KB |
testcase_19 | AC | 2 ms
4,376 KB |
testcase_20 | AC | 1 ms
4,376 KB |
testcase_21 | AC | 1 ms
4,380 KB |
testcase_22 | AC | 1 ms
4,376 KB |
testcase_23 | AC | 2 ms
4,380 KB |
testcase_24 | AC | 2 ms
4,380 KB |
testcase_25 | AC | 2 ms
4,380 KB |
testcase_26 | AC | 2 ms
4,380 KB |
testcase_27 | AC | 2 ms
4,376 KB |
testcase_28 | AC | 1 ms
4,376 KB |
testcase_29 | AC | 2 ms
4,380 KB |
testcase_30 | AC | 1 ms
4,376 KB |
testcase_31 | AC | 1 ms
4,376 KB |
testcase_32 | AC | 1 ms
4,380 KB |
testcase_33 | AC | 2 ms
4,376 KB |
testcase_34 | AC | 1 ms
4,376 KB |
testcase_35 | AC | 2 ms
4,376 KB |
testcase_36 | AC | 2 ms
4,376 KB |
testcase_37 | AC | 1 ms
4,380 KB |
testcase_38 | AC | 2 ms
4,376 KB |
testcase_39 | AC | 2 ms
4,376 KB |
testcase_40 | AC | 2 ms
4,380 KB |
testcase_41 | AC | 2 ms
4,380 KB |
testcase_42 | AC | 1 ms
4,380 KB |
testcase_43 | AC | 2 ms
4,380 KB |
testcase_44 | AC | 2 ms
4,376 KB |
testcase_45 | AC | 2 ms
4,376 KB |
testcase_46 | AC | 2 ms
4,376 KB |
testcase_47 | AC | 2 ms
4,380 KB |
testcase_48 | AC | 2 ms
4,380 KB |
testcase_49 | AC | 2 ms
4,376 KB |
testcase_50 | AC | 2 ms
4,376 KB |
testcase_51 | AC | 2 ms
4,376 KB |
testcase_52 | AC | 2 ms
4,376 KB |
testcase_53 | AC | 2 ms
4,380 KB |
testcase_54 | AC | 3 ms
4,380 KB |
testcase_55 | AC | 2 ms
4,376 KB |
testcase_56 | AC | 1 ms
4,380 KB |
testcase_57 | AC | 2 ms
4,376 KB |
testcase_58 | AC | 2 ms
4,376 KB |
testcase_59 | AC | 1 ms
4,376 KB |
testcase_60 | AC | 2 ms
4,376 KB |
testcase_61 | AC | 2 ms
4,376 KB |
testcase_62 | AC | 1 ms
4,376 KB |
testcase_63 | AC | 9 ms
4,556 KB |
testcase_64 | AC | 3 ms
4,376 KB |
testcase_65 | AC | 6 ms
4,380 KB |
testcase_66 | AC | 6 ms
4,376 KB |
testcase_67 | AC | 3 ms
4,376 KB |
testcase_68 | AC | 5 ms
4,380 KB |
testcase_69 | AC | 7 ms
4,376 KB |
testcase_70 | AC | 4 ms
4,380 KB |
testcase_71 | AC | 3 ms
4,376 KB |
testcase_72 | AC | 6 ms
4,380 KB |
testcase_73 | AC | 3 ms
4,380 KB |
testcase_74 | AC | 7 ms
4,416 KB |
testcase_75 | AC | 5 ms
4,380 KB |
testcase_76 | AC | 3 ms
4,380 KB |
testcase_77 | AC | 5 ms
4,380 KB |
testcase_78 | AC | 9 ms
4,616 KB |
testcase_79 | AC | 9 ms
4,436 KB |
testcase_80 | AC | 8 ms
4,376 KB |
testcase_81 | AC | 9 ms
4,512 KB |
testcase_82 | AC | 8 ms
4,380 KB |
testcase_83 | AC | 120 ms
16,548 KB |
testcase_84 | AC | 111 ms
16,248 KB |
testcase_85 | AC | 69 ms
11,420 KB |
testcase_86 | AC | 93 ms
14,436 KB |
testcase_87 | AC | 112 ms
15,560 KB |
testcase_88 | AC | 14 ms
5,036 KB |
testcase_89 | AC | 123 ms
16,424 KB |
testcase_90 | AC | 64 ms
11,860 KB |
testcase_91 | AC | 49 ms
10,064 KB |
testcase_92 | AC | 25 ms
6,968 KB |
testcase_93 | AC | 90 ms
13,952 KB |
testcase_94 | AC | 78 ms
12,800 KB |
testcase_95 | AC | 79 ms
12,796 KB |
testcase_96 | AC | 120 ms
15,756 KB |
testcase_97 | AC | 38 ms
8,988 KB |
testcase_98 | AC | 102 ms
15,600 KB |
testcase_99 | AC | 55 ms
11,124 KB |
testcase_100 | AC | 116 ms
16,816 KB |
testcase_101 | AC | 23 ms
6,316 KB |
testcase_102 | AC | 11 ms
4,836 KB |
testcase_103 | AC | 23 ms
6,796 KB |
testcase_104 | AC | 35 ms
8,120 KB |
testcase_105 | AC | 86 ms
13,964 KB |
testcase_106 | AC | 44 ms
9,428 KB |
testcase_107 | AC | 109 ms
16,552 KB |
testcase_108 | AC | 102 ms
16,184 KB |
testcase_109 | AC | 81 ms
13,660 KB |
testcase_110 | AC | 70 ms
12,828 KB |
testcase_111 | AC | 73 ms
13,360 KB |
testcase_112 | AC | 31 ms
7,896 KB |
testcase_113 | AC | 71 ms
12,504 KB |
testcase_114 | AC | 40 ms
9,088 KB |
testcase_115 | AC | 14 ms
5,476 KB |
testcase_116 | AC | 48 ms
10,432 KB |
testcase_117 | AC | 32 ms
7,944 KB |
testcase_118 | AC | 100 ms
15,660 KB |
testcase_119 | AC | 53 ms
11,044 KB |
testcase_120 | AC | 92 ms
15,472 KB |
testcase_121 | AC | 25 ms
7,048 KB |
testcase_122 | AC | 48 ms
10,148 KB |
testcase_123 | AC | 1 ms
4,376 KB |
testcase_124 | AC | 161 ms
33,660 KB |
testcase_125 | AC | 179 ms
33,808 KB |
ソースコード
#ifdef LOCAL #define _GLIBCXX_DEBUG #endif #include<bits/stdc++.h> using namespace std; #define rep(i,s,t) for(ll i = (ll)(s); i < (ll)(t); i++) #define rrep(i,s,t) for(ll i = (ll)(s-1);(ll)(t) <= i; i--) #define all(x) (x).begin(), (x).end() typedef long long ll; typedef long double ld; typedef pair<ll,ll> Pll; typedef vector<ll> vl; typedef vector<vl> vvl; typedef vector<vvl> vvvl; constexpr ll INF = numeric_limits<ll>::max()/4; constexpr ll n_max = 2e5+10; #define int ll const long double pi = 3.14159265358979323846; template <typename A, typename B> string to_string(pair<A, B> p); string to_string(const string &s) {return '"' + s + '"';} string to_string(const char *c) {return to_string((string) c);} string to_string(bool b) {return (b ? "true" : "false");} template <size_t N> string to_string(bitset<N> v){ string res = ""; for(size_t i = 0; i < N; i++) res += static_cast<char>('0' + v[i]); return res; } template <typename A> string to_string(A v) { bool first = true; string res = "{"; for(const auto &x : v) { if(!first) res += ", "; first = false; res += to_string(x); } res += "}"; return res; } template <typename A, typename B> string to_string(pair<A, B> p){return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";} void debug_out() {cerr << endl;} template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << to_string(H); debug_out(T...); } #ifdef LOCAL #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #else #define debug(...) 42 #endif template<class T> bool chmax(T &a, T b){if(a < b){a = b; return true;} return false;} template<class T> bool chmin(T &a, T b){if(a > b){a = b; return true;} return false;} void print() { cout << endl; } template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) { cout << head; if (sizeof...(tail) != 0) cout << " "; print(forward<Tail>(tail)...); } template <class T> void print(vector<T> &vec) { for (auto& a : vec) { cout << a; if (&a != &vec.back()) cout << " "; } cout << endl; } template <class T> void print(vector<vector<T>> &df) { for (auto& vec : df) { print(vec); } } signed main(){ cin.tie(nullptr); ios::sync_with_stdio(false); ll n; cin >> n; vector g(n, vector<ll>()); map<Pll, ll> mp; vector<ll> in(n); rep(i, 0, n) { ll u,v; cin >> u >> v; u--; v--; g[u].emplace_back(v); g[v].emplace_back(u); if (u > v) swap(u, v); if(mp.count({u, v})){ cout << 2 << endl; cout << mp[{u, v}] << " " << i + 1 << endl; return 0; } mp[{u, v}] = i + 1; in[u]++; in[v]++; } vector<ll> used(n); queue<ll> que; rep(i, 0, n) if (in[i] == 1) { used[i] = 1; que.emplace(i); } while (!que.empty()){ ll t = que.front(); que.pop(); debug(t); in[t] = 0; for (auto &to :g[t]){ if (used[to]) continue; in[to]--; if(in[to] == 1){ que.emplace(to); used[to] = 1; } } } debug(used); vector<ll> ans, path; auto dfs = [&](auto self, ll now, ll pre = -1) -> void { used[now] = 1; path.emplace_back(now); for (auto &to : g[now]) { if (to == pre) continue; if (used[to]) continue; ans.emplace_back(mp[Pll(min(now, to), max(now, to))]); self(self, to, now); } }; rep(i,0,n)if(!used[i])dfs(dfs, i); debug(ans, path); ll u = path[0], v = path.back(); if (u > v) swap(u, v); ans.emplace_back(mp[{u, v}]); cout << ans.size() << "\n"; print(ans); }