oj.uz

Submission #964025

# Submission time Handle Problem Language Result Execution time Memory
964025 2024-04-16T08:11:06 Z four_specks Pipes (CEOI15_pipes) C++17
0 / 100
 787 ms 37420 KB 
#include <bits/stdc++.h>

using namespace std;

namespace {

template <typename Fun>
struct YCombinator {
  template <typename T>
  YCombinator(T &&_fun) : fun(forward<T>(_fun)) {}

  template <typename... Args>
  decltype(auto) operator()(Args &&...args) {
    return fun(ref(*this), forward<Args>(args)...);
  }

 private:
  Fun fun;
};

template <typename T>
YCombinator(T &&) -> YCombinator<decay_t<T>>;

struct DSU {
  DSU(int n) : e(n, -1) {}

  int find(int x) {
    return e[x] < 0 ? x : e[x] = find(e[x]);
  }

  bool same(int x, int y) {
    return find(x) == find(y);
  }

  bool unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) {
      return false;
    }
    if (e[x] > e[y]) {
      swap(x, y);
    }
    e[x] += e[y];
    e[y] = x;
    return true;
  }

  int size(int x) {
    return -e[find(x)];
  }

  int size() const {
    return (int)e.size();
  }

 private:
  vector<int> e;
};

}  // namespace

void solve() {
  int n, m;
  cin >> n >> m;
  vector<vector<pair<int, int>>> adj(n);
  DSU dsu1(n), dsu2(n);
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    --u;
    --v;
    if (dsu1.unite(u, v) || dsu2.unite(u, v)) {
      adj[u].emplace_back(v, i);
      adj[v].emplace_back(u, i);
    }
  }
  {
    // vector<int> tin(n, -1), low(n);
    // int timer = 0;
    // YCombinator([&](auto self, int u, int p) -> void {
    //   tin[u] = timer++;
    //   low[u] = tin[u];
    //   for (int v : adj[u]) {
    //     if (tin[v] == -1) {
    //       self(v, u);
    //     } else {
    //     }
    //   }
    // })(0, -1);
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  solve();

  return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 504 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 860 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 3952 KB Output is correct
2 Incorrect 73 ms 3408 KB Wrong number of edges
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 6288 KB Output is correct
2 Incorrect 139 ms 7164 KB Wrong number of edges
3 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 10812 KB Output is correct
2 Runtime error 180 ms 16440 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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