oj.uz

답안 #948384

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
948384 2024-03-18T05:10:37 Z vjudge1 Pipes (CEOI15_pipes) C++17
20 / 100
 107 ms 22028 KB 
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define all(x) x.begin(), x.end()
#define size(x) (int)x.size()

template<class S, class T>
bool chmin(S &a, const T &b) {
  return a > b ? (a = b) == b : false;
}
template<class S, class T>
bool chmax(S &a, const T &b) {
  return a < b ? (a = b) == b : false;
}
const short N = 5000;

vector<pair<short, int>> g[N];
bool vis[N];
int tin[N], fup[N], timer;
vector<int> bridges;

short v, p; int idx;
 
void dfs() {
  vis[v] = true;
  tin[v] = fup[v] = ++timer;
  for (auto [to, new_idx] : g[v]) {
    if (idx == new_idx) continue;
    else if (vis[to]) fup[v] = min(fup[v], tin[to]);
    else {
      short pv = v, pp = p; int pidx = idx;
      v = to, p = v, idx = new_idx;
      dfs();
      v = pv, p = pp, idx = pidx;
      fup[v] = min(fup[v], fup[to]);
      if (fup[to] > tin[v]) {
        bridges.push_back(new_idx);
      }
    }
  }
}

signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  short n; int m;
  cin >> n >> m;
  vector<pair<short, short>> vec;
  for (int i = 0; i < m; ++i) {
    short a, b; cin >> a >> b;
    a--, b--;
    g[a].push_back({b, i});
    g[b].push_back({a, i});
    vec.push_back({min(a, b), max(a, b)});
  }
  for (short i = 0; i < n; ++i) {
    if (!vis[i]) {
      v = i, p = -1, idx = -1;
      dfs();
    }
  }
  for (auto i : bridges) {
    cout << vec[i].first + 1 << ' ' << vec[i].second + 1 << '\n';
  }
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 1116 KB Output is correct
2 Correct 3 ms 860 KB Output is correct

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 107 ms 22028 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 860 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 856 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -