oj.uz

Submission #948409

# Submission time Handle Problem Language Result Execution time Memory
948409 2024-03-18T05:26:01 Z vjudge1 Pipes (CEOI15_pipes) C++17
10 / 100
 203 ms 59988 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 int N = 5000;

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

short n; int m;
 
void dfs(short v, short p = -1) {
  vis[v] = true;
  tin[v] = fup[v] = ++timer;
  for (short to = 0; to < n; ++to) {
    if (to == p || to == v || !r[v][to]) continue;
    else if (vis[to]) chmin(fup[v], tin[to]);
    else {
      dfs(to, v);
      chmin(fup[v], fup[to]);
      if (fup[to] > tin[v]) {
        bridges.push_back({v, to});
      }
    }
  }
}

signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    short a, b; cin >> a >> b;
    a--, b--;
    r[a][b] = r[b][a] = true;
    if (us[a][b]) mul[a][b] = mul[b][a] = true;
    us[a][b] = us[b][a] = true;
  }
  for (short i = 0; i < n; ++i) {
    if (!vis[i]) dfs(i);
  }
  for (auto [a, b] : bridges) {
    if (!mul[a][b]) {
      cout << a + 1 << ' ' << b + 1 << '\n';
    }
  }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 4696 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 147 ms 548 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 171 ms 752 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 129 ms 592 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 139 ms 592 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 203 ms 592 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -