oj.uz

Submission #36032

# Submission time Handle Problem Language Result Execution time Memory
36032 2017-12-04T09:36:51 Z funcsr Pipes (CEOI15_pipes) C++14
100 / 100
 448 ms 14872 KB 
#include <bitset>
#include <cassert>
#include <vector>
#include <tuple>
#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], R[100000];
  UnionFind(int N) {
    rep(i, N) U[i] = i, R[i] = 1;
  }
  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;
    if (R[x] < R[y]) swap(x, y);
    U[y] = x;
    R[x] += R[y];
  }
  bool same(int x, int y) {
    return find(x) == find(y);
  }
};

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

bool used[100000];
int R[100000], T[100000];
void dfs(int x, int pe, int r) {
  used[x] = true;
  R[x] = r;
  for (P pp : G[x]) {
    int t = pp._1;
    if (pp._2 == pe) continue;
    if (used[t]) {
      if (R[x] > R[t]) T[x]++, T[t]--;
      continue;
    }
    dfs(t, pp._2, r+1);
  }
}

void dfs2(int x, int p) {
  used[x] = true;
  for (P pp : G[x]) {
    int t = pp._1;
    if (t == p || used[t]) continue;
    dfs2(t, x);
    T[x] += T[t];
  }
  if (p != -1 && T[x] == 0) printf("%d %d\n", x+1, p+1);
}

inline P read2() {
  int u = 0, v = 0;
  char f[15];
  fgets(f, 15, stdin);
  int h = 0;
  while ('0' <= f[h] && f[h] <= '9') u = 10*u+(f[h++]-'0');
  h++;
  while ('0' <= f[h] && f[h] <= '9') v = 10*v+(f[h++]-'0');
  return P(u, v);
}

signed main() {
  scanf("%d%d\n", &N, &M);
  UnionFind uf1(N), uf2(N);
  rep(i, M) {
    int u, v;
    tie(u, v) = read2();
    //scanf("%d %d", &u, &v);
    u--, v--;
    if (!uf1.same(u, v)) {
      G[u].pb(P(v, i)), G[v].pb(P(u, i));
      uf1.unite(u, v);
    }
    else if (!uf2.same(u, v)) {
      G[u].pb(P(v, i)), G[v].pb(P(u, i));
      uf2.unite(u, v);
    }
  }
  rep(i, N) used[i] = false;
  rep(i, N) if (!used[i]) dfs(i, -1, 0);
  rep(i, N) used[i] = false;
  rep(i, N) if (!used[i]) dfs2(i, -1);
  return 0;
}

Compilation message

pipes.cpp: In function 'int main()':
pipes.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d\n", &N, &M);
   ~~~~~^~~~~~~~~~~~~~~~~~
pipes.cpp: In function 'P read2()':
pipes.cpp:68:8: warning: ignoring return value of 'char* fgets(char*, int, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   fgets(f, 15, stdin);
   ~~~~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2736 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3200 KB Output is correct
2 Correct 6 ms 3072 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3064 KB Output is correct
2 Correct 30 ms 2944 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 3896 KB Output is correct
2 Correct 55 ms 3572 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 5560 KB Output is correct
2 Correct 81 ms 5240 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 11384 KB Output is correct
2 Correct 151 ms 8956 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 12728 KB Output is correct
2 Correct 239 ms 9704 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 14864 KB Output is correct
2 Correct 329 ms 11676 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 14872 KB Output is correct
2 Correct 394 ms 11672 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 448 ms 14304 KB Output is correct
2 Correct 418 ms 11552 KB Output is correct