oj.uz

Submission #310458

# Submission time Handle Problem Language Result Execution time Memory
310458 2020-10-07T04:08:19 Z AlexLuchianov Pipes (CEOI15_pipes) C++14
40 / 100
 5000 ms 32760 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 = 17;
int mult[1 + nmax], acc[1 + nmax], sz[1 + nmax];
int level[1 + nmax];

std::vector<int> g[1 + nmax];
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) { 
  for(int h = 0; h < g[node].size(); h++) {
    int to = g[node][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][node]];
  
  for(int h = 0; h < g[node].size(); h++) {
    int to = g[node][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);
    g[x].push_back(y);
    g[y].push_back(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--)
    if(level[y] <= level[x] - (1 << h))
      x = far[h][x];
  if(x == y)
    return x;
  for(int h = sigma; 0 <= h; h--)
    if(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;
}

Compilation message

pipes.cpp: In function 'void clean(int, int)':
pipes.cpp:36:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   for(int h = 0; h < g[node].size(); h++) {
      |                  ~~^~~~~~~~~~~~~~~~
pipes.cpp: In function 'void refresh(int, int)':
pipes.cpp:56:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   for(int h = 0; h < g[node].size(); h++) {
      |                  ~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3584 KB Output is correct
2 Correct 11 ms 3584 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 8824 KB Output is correct
2 Correct 195 ms 8824 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 409 ms 9976 KB Output is correct
2 Correct 466 ms 15824 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 734 ms 12328 KB Output is correct
2 Runtime error 618 ms 21624 KB Memory limit exceeded

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1481 ms 14584 KB Output is correct
2 Runtime error 1457 ms 32760 KB Memory limit exceeded

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2438 ms 16632 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 3617 ms 29432 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 4603 ms 20072 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5041 ms 19832 KB Time limit exceeded
2 Halted 0 ms 0 KB -