oj.uz

답안 #310463

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
310463 2020-10-07T04:20:39 Z AlexLuchianov Pipes (CEOI15_pipes) C++14
80 / 100
 3974 ms 54280 KB 
#include <iostream>
#include <vector>
#include <cassert>
#include <set>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 100000;
int const sigma = 10;
int mult[1 + nmax], acc[1 + nmax], sz[1 + nmax];
int level[1 + nmax];

int ptr = 0;
int start[1 + nmax], nxt[1 + 2 * nmax], val[1 + 2 * nmax];

void add_edge(int node, int to) {
  if(start[node] == 0) {
    start[node] = ++ptr;
    val[ptr] = to;
  } else {
    nxt[++ptr] = start[node];
    start[node] = ptr;
    val[ptr] = to;
  }
}

std::set<std::pair<int,int>> answer;

int far[1 + sigma][1 + nmax];

int jump(int gala) {
  if(mult[gala] != gala)
    mult[gala] = jump(mult[gala]);
  return mult[gala];
}
void initialize(int n) {
  for(int i = 1; i <= n; i++)
    mult[i] = i;
  for(int i = 1;i <= n; i++)
    sz[i] = 1;
}
bool isconnected(int gala, int galb) {
  return jump(gala) == jump(galb);
}

void clean(int node, int parent) { 
  if(0 < start[node]) {
    for(int h = start[node]; 0 < h; h = nxt[h]) {
      int to = val[h];
      if(to != parent) {
        clean(to, node);
        acc[node] += acc[to];
      }
    }
  }
  if(0 < acc[node]) {
    answer.erase({node, parent});
    answer.erase({parent, node});
  }
}

void refresh(int node, int parent) {
  acc[node] = 0;
  level[node] = level[parent] + 1;
  far[0][node] = parent;
  for(int h = 1; h <= sigma; h++)
    far[h][node] = far[h - 1][far[h - 1][far[h - 1][far[h - 1][node]]]];

  for(int h = start[node]; 0 < h; h = nxt[h]) {
    int to = val[h];
    if(to != parent)
      refresh(to, node);
  }
}

bool unite(int x, int y) {
  int gala = jump(x);
  int galb = jump(y);
  if(gala == galb)
    return false;
  else {
    if(sz[galb] < sz[gala]){
      std::swap(x, y);
      std::swap(gala, galb);
    }
    clean(gala, 0);
    add_edge(x, y);
    add_edge(y, x);
    refresh(x, y); 
    mult[gala] = galb;
    sz[galb] += sz[gala];
    answer.insert({x, y});
    return true;
  }
}

int getlca(int x, int y) {
  if(level[x] < level[y])
    std::swap(x, y);
  for(int h = sigma; 0 <= h; h--)
    while(level[y] <= level[x] - (1 << (2 * h)))
      x = far[h][x];
  if(x == y)
    return x;
  for(int h = sigma; 0 <= h; h--)
    while(far[h][x] != far[h][y]) {
      x = far[h][x];
      y = far[h][y];
    }
  return far[0][x];
}

void add_chain(int x, int y) {
  acc[getlca(x, y)] -= 2;
  acc[x]++;
  acc[y]++;
}

int main() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0);

  int n, m;
  std::cin >> n >> m;
  initialize(n);
  for(int i = 1;i <= m; i++) {
    int x, y;
    std::cin >> x >> y;
    if(unite(x, y) == false) 
      add_chain(x, y);
  }
  for(int i = 1;i <= n; i++)
    if(mult[i] == i)
      clean(i, 0);

  for(std::set<std::pair<int,int>>::iterator it = answer.begin(); it != answer.end(); it++)
    std::cout << it->first << " " << it->second << '\n';
  return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 191 ms 896 KB Output is correct
2 Correct 180 ms 888 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 668 ms 3320 KB Output is correct
2 Correct 565 ms 4344 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1079 ms 9076 KB Output is correct
2 Correct 1044 ms 9336 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1840 ms 10464 KB Output is correct
2 Correct 1605 ms 10488 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2730 ms 12664 KB Output is correct
2 Runtime error 2756 ms 54280 KB Memory limit exceeded

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3337 ms 12772 KB Output is correct
2 Correct 3317 ms 16340 KB Output is correct

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3974 ms 12272 KB Output is correct
2 Runtime error 3645 ms 31140 KB Memory limit exceeded