oj.uz

답안 #36019

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
36019 2017-12-04T08:45:59 Z funcsr Pipes (CEOI15_pipes) C++14
0 / 100
 3641 ms 8188 KB 
#include <iostream>
#include <fstream>
#include <bitset>
#include <cassert>
#include <vector>
#define rep(i, n) for (int i=0; i<(n); i++)
#define INF 1145141919
#define pb push_back
#define _1 first
#define _2 second

using namespace std;
typedef pair<int, int> P;

struct UnionFind {
  int U[100000];
  UnionFind(int N) {
    rep(i, N) U[i] = i;
  }
  int find(int x) {
    if (U[x] == x) return x;
    return U[x] = find(U[x]);
  }
  void unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return;
    U[x] = y;
  }
  bool same(int x, int y) {
    return find(x) == find(y);
  }
};

int N, M;
vector<int> G[100000];

bool used[100000];
int R[100000];
void dfs(int x, int p, int r) {
  R[x] = r;
  for (int t : G[x]) {
    if (t == p) continue;
    dfs(t, x, r+1);
  }
}

int T[100000];
int dfs2(int x, int p) {
  for (int t : G[x]) {
    if (t == p) continue;
    T[x] += dfs2(t, x);
  }
  if (p != -1 && T[x] == 0) cout << x+1 << " " << p+1 << "\n";
  int ret = T[x];
  T[x] = INF;
  return ret;
}


signed main() {
  cin >> N >> M;
  UnionFind uf1(N), uf2(N);
  vector<P> backwards;
  rep(i, M) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    if (!uf1.same(u, v)) {
      G[u].pb(v), G[v].pb(u);
      uf1.unite(u, v);
    }
    else if (!uf2.same(u, v)) {
      backwards.pb(P(u, v));
      uf2.unite(u, v);
    }
  }
  rep(i, N) R[i] = -1;
  rep(i, N) if (R[i] == -1) dfs(i, -1, 0);
  for (P p : backwards) {
    int u = p._1, v = p._2;
    if (R[u] > R[v]) swap(u, v);
    T[v]++, T[u]--;
  }
  rep(i, N) if (T[i] != INF) dfs2(i, -1);
  return 0;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 2688 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 3020 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 294 ms 3028 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 513 ms 3252 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 832 ms 3984 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1142 ms 6544 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1830 ms 7188 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2359 ms 8164 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2953 ms 8188 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3641 ms 7948 KB Wrong number of edges
2 Halted 0 ms 0 KB -