結果

問題 No.2301 Namorientation
ユーザー as277575
提出日時 2023-05-12 23:19:23
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,296 bytes
コンパイル時間 1,264 ms
コンパイル使用メモリ 118,092 KB
最終ジャッジ日時 2025-02-12 23:36:57
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 21 WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <cassert>
#include <cstdio>
#include <cmath>
#include <deque>
#include <iostream>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <set>

using namespace::std;


int find_cycle(int n, const vector<vector<int>>& e) {
  vector<bool> visited(n + 1);
  vector<pair<int, int>> q;
  for (int i = 1; i <= n; ++i)
    if (!visited[i]) {
      q.push_back({-1, i});
      while (!q.empty()) {
        auto [u, v] = q.back();
        q.pop_back();
        if (visited[v]) return v;
        visited[v] = 1;
        for (int w : e[v]) if (w != u) q.push_back({v, w});
      }
    }
  return -1;
}

int main() {
  ios::sync_with_stdio(false);
  long long n;
  cin >> n;
  vector<pair<int, int>> input;
  vector<vector<int>> e(n + 1);
  for (int i = 0; i < n; ++i) {
    int a, b;
    cin >> a >> b;
    input.push_back({a, b});
    e[a].push_back(b);
    e[b].push_back(a);
  }
  
  int c = find_cycle(n, e);
  
  vector<int> p(n + 1);
  vector<pair<int, int>> q {{0, c}};
  while (!q.empty()) {
    auto [u, v] = q.back();
    q.pop_back();
    if (p[v]) continue;
    p[v] = u;
    for (int w : e[v]) q.push_back({v, w});
  }
  
  for (const auto [a, b] : input)
    cout << (p[a] == b ? "->" : "<-") << endl;
  
  

  
  return 0;
}
0