結果
問題 | No.1023 Cyclic Tour |
ユーザー | Y17 |
提出日時 | 2020-04-10 23:31:59 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,289 bytes |
コンパイル時間 | 2,535 ms |
コンパイル使用メモリ | 183,132 KB |
実行使用メモリ | 48,952 KB |
最終ジャッジ日時 | 2023-10-14 07:26:08 |
合計ジャッジ時間 | 16,944 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,424 KB |
testcase_01 | AC | 2 ms
5,476 KB |
testcase_02 | AC | 2 ms
5,416 KB |
testcase_03 | AC | 2 ms
5,536 KB |
testcase_04 | AC | 226 ms
36,828 KB |
testcase_05 | AC | 155 ms
22,140 KB |
testcase_06 | AC | 169 ms
22,740 KB |
testcase_07 | AC | 150 ms
22,320 KB |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | AC | 184 ms
41,660 KB |
testcase_12 | AC | 161 ms
41,320 KB |
testcase_13 | AC | 145 ms
39,412 KB |
testcase_14 | WA | - |
testcase_15 | AC | 145 ms
39,716 KB |
testcase_16 | WA | - |
testcase_17 | AC | 264 ms
44,840 KB |
testcase_18 | WA | - |
testcase_19 | AC | 267 ms
42,104 KB |
testcase_20 | AC | 311 ms
42,056 KB |
testcase_21 | AC | 330 ms
43,336 KB |
testcase_22 | AC | 304 ms
46,008 KB |
testcase_23 | AC | 296 ms
46,156 KB |
testcase_24 | AC | 309 ms
48,596 KB |
testcase_25 | WA | - |
testcase_26 | AC | 307 ms
42,124 KB |
testcase_27 | AC | 305 ms
40,128 KB |
testcase_28 | WA | - |
testcase_29 | WA | - |
testcase_30 | WA | - |
testcase_31 | WA | - |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | WA | - |
testcase_35 | WA | - |
testcase_36 | AC | 319 ms
43,624 KB |
testcase_37 | AC | 288 ms
45,936 KB |
testcase_38 | AC | 237 ms
44,876 KB |
testcase_39 | AC | 288 ms
45,264 KB |
testcase_40 | WA | - |
testcase_41 | WA | - |
testcase_42 | WA | - |
testcase_43 | WA | - |
testcase_44 | AC | 229 ms
38,212 KB |
testcase_45 | AC | 170 ms
47,580 KB |
testcase_46 | AC | 172 ms
44,196 KB |
testcase_47 | AC | 248 ms
48,000 KB |
testcase_48 | AC | 237 ms
44,644 KB |
testcase_49 | AC | 227 ms
44,708 KB |
testcase_50 | AC | 223 ms
45,004 KB |
testcase_51 | WA | - |
testcase_52 | WA | - |
ソースコード
#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); for(int i = 1;i < n;i++){ if(x[0] == x[i]){ cout << "Yes" << endl; return 0; } } StronglyConnectedComponents<UnWeightedGraph> scc(graph); scc.build(tmp2); for(int i = 0;i < m;i++){ if(c[i] == 2 && scc[a[i]] != scc[b[i]]){ tmp2[scc[a[i]]].push_back(scc[b[i]]); }else if(c[i] == 2 && scc[0] == scc[a[i]] && scc[0] == scc[b[i]]){ cout << "Yes" << endl; return 0; } } StronglyConnectedComponents<UnWeightedGraph> scc2(tmp2); scc2.build(tmp3); for(int i = 1;i < tmp2.size();i++){ if(scc2[0] == scc2[i]){ cout << "Yes" << endl; return 0; } } cout << "No" << endl; return 0; }