Submission #310458

#	Time	Username	Problem	Language	Result	Execution time	Memory
310458		AlexLuchianov	Pipes (CEOI15_pipes)	C++14	40 / 100	5041 ms	32760 KiB

pipes

#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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10