oj.uz

Submission #310464

# Submission time Handle Problem Language Result Execution time Memory
310464 2020-10-07T04:22:08 Z AlexLuchianov Pipes (CEOI15_pipes) C++14
100 / 100
 3418 ms 12284 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 = 8;
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

# Verdict Execution time Memory 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

# Verdict Execution time Memory Grader output
1 Correct 7 ms 896 KB Output is correct
2 Correct 7 ms 896 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 768 KB Output is correct
2 Correct 176 ms 768 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 1656 KB Output is correct
2 Correct 388 ms 1656 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 636 ms 3224 KB Output is correct
2 Correct 529 ms 3964 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1002 ms 8696 KB Output is correct
2 Correct 898 ms 8568 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1601 ms 9976 KB Output is correct
2 Correct 1473 ms 10060 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2268 ms 12096 KB Output is correct
2 Correct 2225 ms 12284 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2819 ms 11896 KB Output is correct
2 Correct 2814 ms 12024 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3418 ms 11428 KB Output is correct
2 Correct 3085 ms 12280 KB Output is correct