oj.uz

Submission #964028

# Submission time Handle Problem Language Result Execution time Memory
964028 2024-04-16T08:15:23 Z four_specks Pipes (CEOI15_pipes) C++17
0 / 100
 816 ms 65536 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<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);
      adj[v].emplace_back(u);
    }
  }
  {
    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 344 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 604 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 692 KB Output is correct
2 Incorrect 82 ms 676 KB Wrong number of edges
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 1116 KB Output is correct
2 Incorrect 142 ms 1120 KB Wrong number of edges
3 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 2140 KB Output is correct
2 Incorrect 155 ms 2576 KB Wrong number of edges
3 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 5964 KB Output is correct
2 Runtime error 234 ms 24100 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 6720 KB Output is correct
2 Runtime error 419 ms 39432 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 546 ms 8316 KB Output is correct
2 Runtime error 492 ms 49716 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 652 ms 8312 KB Output is correct
2 Runtime error 654 ms 61388 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 816 ms 7692 KB Output is correct
2 Runtime error 804 ms 65536 KB Memory limit exceeded
3 Halted 0 ms 0 KB -