답안 #35975 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
35975	2017-12-04T04:01:00 Z	funcsr	Pipes (CEOI15_pipes)	C++14	90 / 100	5000 ms	14016 KB

pipes

#include <bitset>
#include <cassert>
#include <vector>
#define rep(i, n) for (int i=0; i<(n); i++)
#define INF 1145141919
#define pb push_back

using namespace std;
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];

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

inline int lca(int x, int y) {
  if (R[x] < R[y]) swap(x, y);
  for (int b=16; b>=0; b--) if ((R[x]-R[y])>>b) x = U[b][x];
  if (x == y) return x;
  for (int b=16; b>=0; b--) if (U[b][x] != U[b][y]) x = U[b][x], y = U[b][y];
  return U[0][x];
}

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) printf("%d %d\n", x+1, p+1);
  int ret = T[x];
  T[x] = INF;
  return ret;
}


signed main() {
  auto f = fopen("/dev/stdin", "r");
  fscanf(f, "%d %d", &N, &M);
  auto uf = new UnionFind(N);
  auto backward = new bitset<6000000>();
  rep(i, M) {
    int u, v;
    fscanf(f, "%d %d", &u, &v);
    u--, v--;
    if (uf->same(u, v)) {
      backward->set(i);
    }
    else {
      uf->unite(u, v);
      G[u].pb(v);
      G[v].pb(u);
    }
  }
  delete uf;
  rep(i, N) R[i] = -1;
  rep(i, N) if (R[i] == -1) dfs(i, -1, 0);
  rep(k, 16) rep(i, N) {
    if (U[k][i] == -1) U[k+1][i] = -1;
    U[k+1][i] = U[k][U[k][i]];
  }

  fseek(f, 0, 0);
  int nn, nm;
  nm=0;
  fscanf(f, "%d %d", &nn, &nm);
  assert(N == nn && M == nm);
  rep(i, M) {
    int u, v;
    fscanf(f, "%d %d", &u, &v);
    u--, v--;
    if (backward->test(i)) {
      T[u]++;
      T[v]++;
      T[lca(u, v)]-=2;
    }
  }
  delete backward;
  rep(i, N) if (T[i] != INF) dfs2(i, -1);
  return 0;
}

Compilation message

pipes.cpp: In function 'int main()':
pipes.cpp:65:9: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   fscanf(f, "%d %d", &N, &M);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~
pipes.cpp:70:11: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf(f, "%d %d", &u, &v);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~
pipes.cpp:92:9: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   fscanf(f, "%d %d", &nn, &nm);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~
pipes.cpp:96:11: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf(f, "%d %d", &u, &v);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	3456 KB	Output is correct
2	Correct	4 ms	3456 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	3988 KB	Output is correct
2	Correct	17 ms	3948 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	302 ms	3816 KB	Output is correct
2	Correct	306 ms	3816 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	616 ms	4520 KB	Output is correct
2	Correct	706 ms	4432 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1037 ms	5988 KB	Output is correct
2	Correct	854 ms	6588 KB	Output is correct

Subtask #6
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1510 ms	10900 KB	Output is correct
2	Correct	1275 ms	10900 KB	Output is correct

Subtask #7
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2560 ms	12000 KB	Output is correct
2	Correct	2300 ms	11944 KB	Output is correct

Subtask #8
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3537 ms	13872 KB	Output is correct
2	Correct	3212 ms	14016 KB	Output is correct

Subtask #9
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4462 ms	13904 KB	Output is correct
2	Correct	4457 ms	14016 KB	Output is correct

Subtask #10
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	5041 ms	13552 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-