#462341 (C++17) No.1023 Cyclic Tour

提出ソース

結果

問題	No.1023 Cyclic Tour
ユーザー	👑 emthrm
提出日時	2020-04-10 22:58:48
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	388 ms / 2,000 ms
コード長	3,199 bytes
コンパイル時間	3,035 ms
コンパイル使用メモリ	219,256 KB
実行使用メモリ	24,316 KB
最終ジャッジ日時	2023-10-14 04:03:55
合計ジャッジ時間	17,722 ms
ジャッジサーバーID （参考情報）	judge13 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,348 KB
testcase_01	AC	2 ms 4,348 KB
testcase_02	AC	2 ms 4,352 KB
testcase_03	AC	1 ms 4,348 KB
testcase_04	AC	88 ms 13,532 KB
testcase_05	AC	89 ms 13,504 KB
testcase_06	AC	102 ms 14,400 KB
testcase_07	AC	94 ms 13,952 KB
testcase_08	AC	146 ms 15,436 KB
testcase_09	AC	148 ms 16,016 KB
testcase_10	AC	143 ms 15,876 KB
testcase_11	AC	159 ms 17,040 KB
testcase_12	AC	145 ms 16,968 KB
testcase_13	AC	131 ms 16,180 KB
testcase_14	AC	60 ms 7,800 KB
testcase_15	AC	136 ms 16,596 KB
testcase_16	AC	220 ms 12,728 KB
testcase_17	AC	341 ms 22,692 KB
testcase_18	AC	224 ms 13,320 KB
testcase_19	AC	189 ms 12,308 KB
testcase_20	AC	315 ms 20,380 KB
testcase_21	AC	323 ms 20,576 KB
testcase_22	AC	319 ms 21,952 KB
testcase_23	AC	351 ms 22,544 KB
testcase_24	AC	388 ms 24,316 KB
testcase_25	AC	323 ms 20,364 KB
testcase_26	AC	318 ms 20,816 KB
testcase_27	AC	280 ms 19,912 KB
testcase_28	AC	378 ms 23,736 KB
testcase_29	AC	352 ms 23,384 KB
testcase_30	AC	388 ms 23,812 KB
testcase_31	AC	359 ms 22,520 KB
testcase_32	AC	358 ms 22,884 KB
testcase_33	AC	385 ms 24,004 KB
testcase_34	AC	290 ms 18,428 KB
testcase_35	AC	294 ms 19,140 KB
testcase_36	AC	325 ms 21,180 KB
testcase_37	AC	337 ms 22,144 KB
testcase_38	AC	325 ms 22,772 KB
testcase_39	AC	340 ms 22,148 KB
testcase_40	AC	362 ms 22,424 KB
testcase_41	AC	354 ms 22,264 KB
testcase_42	AC	334 ms 19,768 KB
testcase_43	AC	282 ms 13,180 KB
testcase_44	AC	104 ms 13,340 KB
testcase_45	AC	136 ms 18,024 KB
testcase_46	AC	121 ms 17,144 KB
testcase_47	AC	116 ms 19,924 KB
testcase_48	AC	230 ms 21,368 KB
testcase_49	AC	240 ms 21,336 KB
testcase_50	AC	225 ms 21,408 KB
testcase_51	AC	223 ms 21,632 KB
testcase_52	AC	238 ms 20,744 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
using ll = long long;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-8;
const int MOD = 1000000007;
// const int MOD = 998244353;
const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
const int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1};
template <typename T, typename U> inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U> inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; }
struct IOSetup {
  IOSetup() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
  }
} iosetup;

using CostType = char;
struct Edge {
  int src, dst; CostType cost;
  Edge(int src, int dst, CostType cost = 0) : src(src), dst(dst), cost(cost) {}
  inline bool operator<(const Edge &x) const {
    return cost != x.cost ? cost < x.cost : dst != x.dst ? dst < x.dst : src < x.src;
  }
  inline bool operator<=(const Edge &x) const { return !(x < *this); }
  inline bool operator>(const Edge &x) const { return x < *this; }
  inline bool operator>=(const Edge &x) const { return !(*this < x); }
};

vector<int> topological_sort(const vector<vector<Edge>> &graph) {
  int n = graph.size();
  vector<int> deg(n, 0);
  REP(i, n) {
    for (const Edge &e : graph[i]) ++deg[e.dst];
  }
  queue<int> que;
  REP(i, n) {
    if (deg[i] == 0) que.emplace(i);
  }
  vector<int> res;
  while (!que.empty()) {
    int ver = que.front(); que.pop();
    res.emplace_back(ver);
    for (const Edge &e : graph[ver]) {
      if (--deg[e.dst] == 0) que.emplace(e.dst);
    }
  }
  return res.size() == n ? res : vector<int>();
}

int main() {
  int n, m; cin >> n >> m;
  set<pair<int, int>> und, dir;
  while (m--) {
    int a, b, c; cin >> a >> b >> c; --a; --b;
    (c == 1 ? und : dir).emplace(a, b);
  }
  vector<int> p, q;
  for (auto [a, b] : dir) {
    if (und.count(make_pair(a, b)) == 1 || und.count(make_pair(b, a)) == 1 || dir.count(make_pair(b, a)) == 1) {
      cout << "Yes\n";
      return 0;
    }
    p.emplace_back(a);
    q.emplace_back(b);
  }
  vector<vector<int>> und_graph(n);
  for (auto [a, b] : und) {
    und_graph[a].emplace_back(b);
    und_graph[b].emplace_back(a);
  }
  vector<int> id(n, -1);
  int sz = 0;
  REP(i, n) {
    if (id[i] != -1) continue;
    function<void(int, int)> dfs = [&](int par, int ver) {
      for (int e : und_graph[ver]) {
        if (e == par) continue;
        if (id[e] == -1) {
          id[e] = id[i];
          dfs(ver, e);
        } else {
          cout << "Yes\n";
          exit(0);
        }
      }
    };
    id[i] = sz++;
    dfs(-1, i);
  }
  // REP(i, n) cout << id[i] << " \n"[i + 1 == n];
  vector<vector<Edge>> graph(sz);
  REP(i, p.size()) {
    int a = id[p[i]], b = id[q[i]];
    if (a == b) {
      cout << "Yes\n";
      return 0;
    }
    // cout << a << ' ' << b << '\n';
    graph[a].emplace_back(a, b);
  }
  cout << (topological_sort(graph).empty() ? "Yes\n" : "No\n");
  return 0;
}

yukicoder

結果

テストケース

ソースコード