oj.uz

Submission #948292

# Submission time Handle Problem Language Result Execution time Memory
948292 2024-03-18T03:42:40 Z vjudge1 Pipes (CEOI15_pipes) C++17
0 / 100
 843 ms 65536 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;
}

vector<vector<int>> g;
vector<bool> vis;
vector<int> tin, fup;
int timer;
map<pair<int, int>, bool> is_bridge;
 
void dfs(int v, int p = -1) {
  vis[v] = true;
  tin[v] = fup[v] = ++timer;
  for (auto to : g[v]) {
    if (to == p) continue;
    else if (vis[to]) chmin(fup[v], tin[to]);
    else {
      dfs(to, v);
      chmin(fup[v], fup[to]);
      if (fup[to] > tin[v]) {
        is_bridge[{v, to}] = is_bridge[{to, v}] = true;
      }
    }
  }
}

signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, m; cin >> n >> m;
  g.resize(n);
  vis.assign(n, false);
  tin.resize(n), fup.resize(n);
  vector<pair<int, int>> v, res;
  for (int i = 0; i < m; ++i) {
    int a, b; cin >> a >> b;
    a--, b--;
    g[a].push_back(b);
    g[b].push_back(a);
    v.push_back({min(a, b), max(a, b)});
  }
  for (int i = 0; i < n; ++i) {
    if (!vis[i]) dfs(i);
  }
  while (!v.empty()) {
    auto [a, b] = v.back();
    v.pop_back();
    if (is_bridge[{a, b}]) {
      res.push_back({a, b});
    }
  }
  reverse(all(res));
  cout << size(res) << '\n';
  for (auto [a, b] : res) {
    cout << a + 1 << ' ' << b + 1 << '\n';
  }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 1884 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 575 ms 54632 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 685 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 578 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 562 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 761 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 843 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 742 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 724 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -