結果
問題 | No.1023 Cyclic Tour |
ユーザー | RTnF |
提出日時 | 2020-04-10 23:00:51 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 102 ms / 2,000 ms |
コード長 | 5,408 bytes |
コンパイル時間 | 2,509 ms |
コンパイル使用メモリ | 209,516 KB |
実行使用メモリ | 23,032 KB |
最終ジャッジ日時 | 2023-10-14 04:09:07 |
合計ジャッジ時間 | 9,303 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,352 KB |
testcase_01 | AC | 2 ms
4,348 KB |
testcase_02 | AC | 2 ms
4,348 KB |
testcase_03 | AC | 2 ms
4,348 KB |
testcase_04 | AC | 51 ms
14,940 KB |
testcase_05 | AC | 49 ms
14,876 KB |
testcase_06 | AC | 57 ms
16,520 KB |
testcase_07 | AC | 52 ms
15,664 KB |
testcase_08 | AC | 54 ms
15,156 KB |
testcase_09 | AC | 56 ms
14,544 KB |
testcase_10 | AC | 51 ms
14,812 KB |
testcase_11 | AC | 57 ms
15,576 KB |
testcase_12 | AC | 53 ms
15,456 KB |
testcase_13 | AC | 51 ms
14,872 KB |
testcase_14 | AC | 51 ms
14,720 KB |
testcase_15 | AC | 54 ms
15,008 KB |
testcase_16 | AC | 99 ms
21,992 KB |
testcase_17 | AC | 98 ms
22,412 KB |
testcase_18 | AC | 102 ms
22,684 KB |
testcase_19 | AC | 92 ms
22,068 KB |
testcase_20 | AC | 96 ms
21,016 KB |
testcase_21 | AC | 101 ms
21,216 KB |
testcase_22 | AC | 93 ms
20,600 KB |
testcase_23 | AC | 95 ms
21,336 KB |
testcase_24 | AC | 92 ms
21,616 KB |
testcase_25 | AC | 91 ms
21,024 KB |
testcase_26 | AC | 92 ms
20,628 KB |
testcase_27 | AC | 91 ms
19,476 KB |
testcase_28 | AC | 91 ms
21,072 KB |
testcase_29 | AC | 92 ms
20,980 KB |
testcase_30 | AC | 96 ms
21,556 KB |
testcase_31 | AC | 92 ms
20,748 KB |
testcase_32 | AC | 90 ms
21,820 KB |
testcase_33 | AC | 93 ms
22,036 KB |
testcase_34 | AC | 72 ms
15,516 KB |
testcase_35 | AC | 76 ms
17,612 KB |
testcase_36 | AC | 92 ms
20,824 KB |
testcase_37 | AC | 89 ms
21,040 KB |
testcase_38 | AC | 89 ms
20,608 KB |
testcase_39 | AC | 93 ms
20,504 KB |
testcase_40 | AC | 90 ms
20,412 KB |
testcase_41 | AC | 91 ms
20,608 KB |
testcase_42 | AC | 95 ms
20,812 KB |
testcase_43 | AC | 91 ms
20,284 KB |
testcase_44 | AC | 59 ms
15,336 KB |
testcase_45 | AC | 53 ms
21,708 KB |
testcase_46 | AC | 53 ms
21,816 KB |
testcase_47 | AC | 60 ms
23,032 KB |
testcase_48 | AC | 81 ms
21,564 KB |
testcase_49 | AC | 77 ms
19,416 KB |
testcase_50 | AC | 81 ms
21,220 KB |
testcase_51 | AC | 83 ms
20,952 KB |
testcase_52 | AC | 83 ms
21,000 KB |
ソースコード
#pragma region template #include <bits/stdc++.h> using namespace std; using ll = long long; using ull = unsigned long long; using ld = long double; using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>; using vll = vector<ll>; using vvll = vector<vll>; using vvvll = vector<vvll>; using vld = vector<ld>; using vvld = vector<vld>; using vvvld = vector<vvld>; using vs = vector<string>; using pll = pair<ll, ll>; using vp = vector<pll>; template <typename T> using pqrev = priority_queue<T, vector<T>, greater<T>>; #define rep(i, n) for (ll i = 0, i##_end = (n); i < i##_end; i++) #define repb(i, n) for (ll i = (n)-1; i >= 0; i--) #define repr(i, a, b) for (ll i = (a), i##_end = (b); i < i##_end; i++) #define reprb(i, a, b) for (ll i = (b)-1, i##_end = (a); i >= i##_end; i--) #define ALL(a) (a).begin(), (a).end() #define SZ(x) ((ll)(x).size()) //* constexpr ll MOD = 1e9 + 7; /*/ constexpr ll MOD = 998244353; //*/ constexpr ll INF = 1e+18; constexpr ld EPS = 1e-12L; constexpr ld PI = 3.14159265358979323846L; constexpr ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; } constexpr ll LCM(ll a, ll b) { return a / GCD(a, b) * b; } template <typename S, typename T> constexpr bool chmax(S &a, const T &b) { if (a < b) { a = b; return 1; } return 0; } template <typename S, typename T> constexpr bool chmin(S &a, const T &b) { if (b < a) { a = b; return 1; } return 0; } #ifdef OJ_LOCAL #include "dump.hpp" #else #define dump(...) ((void)0) #endif template <typename T> bool print_(const T &a) { cout << a; return true; } template <typename T> bool print_(const vector<T> &vec) { for (auto &a : vec) { cout << a; if (&a != &vec.back()) { cout << " "; } } return false; } template <typename T> bool print_(const vector<vector<T>> &vv) { for (auto &v : vv) { for (auto &a : v) { cout << a; if (&a != &v.back()) { cout << " "; } } if (&v != &vv.back()) { cout << "\n"; } } return false; } void print() { cout << "\n"; } template <typename Head, typename... Tail> void print(Head &&head, Tail &&... tail) { bool f = print_(head); if (sizeof...(tail) != 0) { cout << (f ? " " : "\n"); } print(forward<Tail>(tail)...); } #pragma endregion template <typename T> struct Edge { int from, to; T cost; int id; Edge(int from_, int to_, T cost_, int id_) : from(from_), to(to_), cost(cost_), id(id_) {} Edge(int from_, int to_, T cost_) : from(from_), to(to_), cost(cost_) {} Edge(int from_, int to_) : from(from_), to(to_), cost(1) {} bool operator<(const Edge<T> &r) { return cost < r.cost; } }; template <typename T> ostream &operator<<(ostream &os, Edge<T> edge) { os << edge.from << " -> " << edge.to << " (" << edge.cost << ")"; return os; } // グラフテンプレート(隣接リスト) template <typename E = Edge<ll>> struct GraphL { // 頂点数、辺数 int n, m; // 隣接リスト vector<vector<E>> adj; GraphL(int n_) : n(n_), m(0), adj(n_) {} template <typename... Args> void add_edge(int from, int to, Args... args) { adj[from].emplace_back(from, to, args...); m++; } vector<E> &operator[](int i) { return adj[i]; } }; template <typename E = Edge<ll>> ostream &operator<<(ostream &os, GraphL<E> graph) { os << "V = " << graph.n << ", E = " << graph.m << "\n"; for (const auto &ev : graph.adj) { for (const auto &e : ev) { os << e << "\n"; } } return os; } void Pr(bool f){ cout << (f ? "Yes" : "No") << "\n"; exit(0); } template <typename E> vector<ll> TopologicalSort(GraphL<E> &graph) { vector<ll> ret; vector<bool> visited(graph.n, false); auto dfs = [&](auto &Self, int node) -> void { if(!visited[node]){ visited[node] = true; for (auto &&e : graph.adj[node]) { Self(Self, e.to); } ret.emplace_back(node); } }; for (int i = 0; i < graph.n; i++) { dfs(dfs, i); } reverse(ret.begin(), ret.end()); vector<ll> chk(graph.n); for (int i = 0; i < graph.n; i++) { chk[ret[i]] = i; } for (int i = 0; i < graph.n; i++) { for(auto&& e: graph.adj[i]) { if(chk[i] >= chk[e.to]){ return vector<ll>(); } } } return ret; } int main() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); ll n, m; cin >> n >> m; vll a(m), b(m), c(m); rep(i, m){ cin >> a[i] >> b[i] >> c[i]; a[i]--; b[i]--; } GraphL<> g1(n); rep(i, m){ if(c[i] == 1){ g1.add_edge(a[i], b[i]); g1.add_edge(b[i], a[i]); } } vll col(n, 0); vector<bool> visited(n, false); auto dfs = [&](auto& Self, int node, int cc, int p = -1) -> void{ visited[node] = true; col[node] = cc; for(auto&& e: g1[node]){ if(!visited[e.to]){ Self(Self, e.to, cc, node); }else if(e.to != p){ Pr(1); } } }; ll cc = 0; rep(i, n){ if(!visited[i]){ dfs(dfs, i, cc); cc++; } } GraphL<> g2(cc); auto dfs2 = [&](auto& Self, int node, int p = -1) -> void{ visited[node] = true; for(auto&& e: g2[node]){ if(!visited[e.to]){ Self(Self, e.to); }else if(e.to != p){ Pr(1); } } }; rep(i, m){ if(c[i] == 2){ g2.add_edge(col[a[i]], col[b[i]]); } } fill(ALL(visited), 0); dump(g2); Pr(SZ(TopologicalSort(g2)) == 0); }