結果
問題 | No.1023 Cyclic Tour |
ユーザー | Y17 |
提出日時 | 2020-04-11 00:00:53 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 293 ms / 2,000 ms |
コード長 | 4,327 bytes |
コンパイル時間 | 1,785 ms |
コンパイル使用メモリ | 184,132 KB |
実行使用メモリ | 50,364 KB |
最終ジャッジ日時 | 2023-10-14 08:45:56 |
合計ジャッジ時間 | 14,814 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,444 KB |
testcase_01 | AC | 2 ms
5,496 KB |
testcase_02 | AC | 1 ms
5,756 KB |
testcase_03 | AC | 2 ms
5,724 KB |
testcase_04 | AC | 115 ms
22,772 KB |
testcase_05 | AC | 113 ms
22,944 KB |
testcase_06 | AC | 113 ms
23,664 KB |
testcase_07 | AC | 118 ms
23,112 KB |
testcase_08 | AC | 115 ms
29,760 KB |
testcase_09 | AC | 140 ms
40,600 KB |
testcase_10 | AC | 138 ms
40,820 KB |
testcase_11 | AC | 153 ms
42,680 KB |
testcase_12 | AC | 122 ms
43,028 KB |
testcase_13 | AC | 118 ms
40,704 KB |
testcase_14 | AC | 122 ms
40,368 KB |
testcase_15 | AC | 128 ms
40,864 KB |
testcase_16 | AC | 221 ms
46,144 KB |
testcase_17 | AC | 232 ms
46,560 KB |
testcase_18 | AC | 222 ms
43,840 KB |
testcase_19 | AC | 218 ms
43,232 KB |
testcase_20 | AC | 249 ms
43,624 KB |
testcase_21 | AC | 258 ms
44,912 KB |
testcase_22 | AC | 265 ms
47,152 KB |
testcase_23 | AC | 275 ms
47,576 KB |
testcase_24 | AC | 258 ms
50,364 KB |
testcase_25 | AC | 276 ms
43,752 KB |
testcase_26 | AC | 265 ms
43,680 KB |
testcase_27 | AC | 293 ms
41,532 KB |
testcase_28 | AC | 259 ms
48,796 KB |
testcase_29 | AC | 245 ms
47,680 KB |
testcase_30 | AC | 272 ms
50,188 KB |
testcase_31 | AC | 257 ms
49,080 KB |
testcase_32 | AC | 245 ms
47,700 KB |
testcase_33 | AC | 261 ms
50,364 KB |
testcase_34 | AC | 171 ms
22,812 KB |
testcase_35 | AC | 189 ms
25,104 KB |
testcase_36 | AC | 267 ms
44,948 KB |
testcase_37 | AC | 252 ms
47,560 KB |
testcase_38 | AC | 228 ms
46,412 KB |
testcase_39 | AC | 255 ms
46,392 KB |
testcase_40 | AC | 255 ms
46,900 KB |
testcase_41 | AC | 261 ms
46,956 KB |
testcase_42 | AC | 265 ms
39,904 KB |
testcase_43 | AC | 169 ms
30,176 KB |
testcase_44 | AC | 191 ms
38,760 KB |
testcase_45 | AC | 157 ms
49,128 KB |
testcase_46 | AC | 149 ms
45,000 KB |
testcase_47 | AC | 194 ms
48,596 KB |
testcase_48 | AC | 210 ms
45,248 KB |
testcase_49 | AC | 220 ms
45,568 KB |
testcase_50 | AC | 211 ms
45,944 KB |
testcase_51 | AC | 203 ms
41,340 KB |
testcase_52 | AC | 206 ms
41,776 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define int long long template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; } template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; } using UnWeightedGraph = vector< vector< int > >; template< typename G > struct StronglyConnectedComponents { const G &g; UnWeightedGraph gg, rg; vector< int > comp, order, used; StronglyConnectedComponents(G &g) : g(g), gg(g.size()), rg(g.size()), comp(g.size(), -1), used(g.size()) { for(int i = 0; i < g.size(); i++) { for(auto e : g[i]) { gg[i].emplace_back((int) e); rg[(int) e].emplace_back(i); } } } int operator[](int k) { return comp[k]; } void dfs(int idx) { if(used[idx]) return; used[idx] = true; for(int to : gg[idx]) dfs(to); order.push_back(idx); } void rdfs(int idx, int cnt) { if(comp[idx] != -1) return; comp[idx] = cnt; for(int to : rg[idx]) rdfs(to, cnt); } void build(UnWeightedGraph &t) { for(int i = 0; i < gg.size(); i++) dfs(i); reverse(begin(order), end(order)); int ptr = 0; for(int i : order) if(comp[i] == -1) rdfs(i, ptr), ptr++; t.resize(ptr); for(int i = 0; i < g.size(); i++) { for(auto &to : g[i]) { int x = comp[i], y = comp[to]; if(x == y) continue; t[x].push_back(y); } } } }; template< typename G > struct LowLink { const G &g; vector< int > used, ord, low; vector< int > articulation; vector< pair< int, int > > bridge; LowLink(const G &g) : g(g) {} int dfs(int idx, int k, int par) { used[idx] = true; ord[idx] = k++; low[idx] = ord[idx]; bool is_articulation = false; int cnt = 0; for(auto &to : g[idx]) { if(!used[to]) { ++cnt; k = dfs(to, k, idx); low[idx] = min(low[idx], low[to]); is_articulation |= ~par && low[to] >= ord[idx]; if(ord[idx] < low[to]) bridge.emplace_back(minmax(idx, (int) to)); } else if(to != par) { low[idx] = min(low[idx], ord[to]); } } is_articulation |= par == -1 && cnt > 1; if(is_articulation) articulation.push_back(idx); return k; } virtual void build() { used.assign(g.size(), 0); ord.assign(g.size(), 0); low.assign(g.size(), 0); int k = 0; for(int i = 0; i < g.size(); i++) { if(!used[i]) k = dfs(i, k, -1); } } }; template< typename G > struct TwoEdgeConnectedComponents : LowLink< G > { using LL = LowLink< G >; vector< int > comp; TwoEdgeConnectedComponents(const G &g) : LL(g) {} int operator[](const int &k) { return comp[k]; } void dfs(int idx, int par, int &k) { if(~par && this->ord[par] >= this->low[idx]) comp[idx] = comp[par]; else comp[idx] = k++; for(auto &to : this->g[idx]) { if(comp[to] == -1) dfs(to, idx, k); } } void build(UnWeightedGraph &t) { LL::build(); comp.assign(this->g.size(), -1); int k = 0; for(int i = 0; i < comp.size(); i++) { if(comp[i] == -1) dfs(i, -1, k); } t.resize(k); for(auto &e : this->bridge) { int x = comp[e.first], y = comp[e.second]; t[x].push_back(y); t[y].push_back(x); } } }; int a[200010]; int b[200010]; int c[200010]; signed main(){ int n, m; cin >> n >> m; UnWeightedGraph graph(n); for(int i = 0;i < m;i++){ cin >> a[i] >> b[i] >> c[i]; a[i]--; b[i]--; if(c[i] == 1){ graph[a[i]].push_back(b[i]); graph[b[i]].push_back(a[i]); } } TwoEdgeConnectedComponents<UnWeightedGraph> x(graph); UnWeightedGraph tmp, tmp2, tmp3; x.build(tmp); vector<int> cnt(n, 0); for(int i = 0;i < n;i++){ cnt[x[i]]++; if(cnt[x[i]] > 1){ cout << "Yes" << endl; return 0; } } StronglyConnectedComponents<UnWeightedGraph> scc(graph); scc.build(tmp2); for(int i = 0;i < m;i++){ if(c[i] == 2){ if(scc[a[i]] == scc[b[i]]){ cout << "Yes" << endl; return 0; }else{ tmp2[scc[a[i]]].push_back(scc[b[i]]); } } } StronglyConnectedComponents<UnWeightedGraph> scc2(tmp2); scc2.build(tmp3); vector<int> cnt2(n, 0); for(int i = 0;i < tmp2.size();i++){ cnt2[scc2[i]]++; if(cnt2[scc2[i]] > 1){ cout << "Yes" << endl; return 0; } } cout << "No" << endl; return 0; }