Submission #948352

#	Time	Username	Problem	Language	Result	Execution time	Memory
948352		vjudge1	Pipes (CEOI15_pipes)	C++17	20 / 100	3 ms	1884 KiB

pipes

#include <bits/stdc++.h>
using namespace std;
#define int short
#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<pair<int, int>>> g;
vector<bool> vis;
vector<int> tin, fup;
int timer;
set<pair<int, int>> st;
 
void dfs(int v, int p = -1, int idx = -1) {
  vis[v] = true;
  tin[v] = fup[v] = ++timer;
  for (auto [to, new_idx] : g[v]) {
    if (idx == new_idx) continue;
    else if (vis[to]) chmin(fup[v], tin[to]);
    else {
      dfs(to, v, new_idx);
      chmin(fup[v], fup[to]);
      if (fup[to] > tin[v]) {
        st.insert({min(v, to), max(to, v)});
      }
    }
  }
}

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;
  for (int i = 0; i < m; ++i) {
    int a, b; cin >> a >> b;
    a--, b--;
    g[a].push_back({b, i});
    g[b].push_back({a, i});
    v.push_back({min(a, b), max(a, b)});
  }
  for (int i = 0; i < n; ++i) {
    if (!vis[i]) dfs(i);
  }
  for (auto [a, b] : v) {
    if (st.count({a, b})) {
      cout << a + 1 << ' ' << b + 1 << '\n';
    }
  }
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10