Submission #291994

#	Time	Username	Problem	Language	Result	Execution time	Memory
291994		AlexLuchianov	Simurgh (IOI17_simurgh)	C++14	100 / 100	386 ms	5624 KiB

simurgh

#include "simurgh.h"
#include <cassert>
#include <cmath>
#include <cassert>
#include <algorithm>
#include <vector>
#include <iostream>

class Dsu{
public:
  std::vector<int> mult;
  Dsu(int n) {
    mult.resize(n);
    for(int i = 0; i < n; i++)
      mult[i] = i;
  }
  int jump(int gala) {
    if(gala != mult[gala])
      mult[gala] = jump(mult[gala]);
    return mult[gala];
  }
  bool connect(int gala, int galb) {
    return jump(gala) == jump(galb);
  }
  void unite(int gala, int galb) {
    gala = jump(gala);
    galb = jump(galb);
    if(gala == galb)
      return ;
    mult[gala] = galb;
  }
};

std::vector<std::pair<int,int>> edges;

std::vector<int> get_skeleton(int n) {
  Dsu dsu(n);
  std::vector<int> skeleton;

  for(int i = 0; i < edges.size(); i++) {
    int x = edges[i].first;
    int y = edges[i].second;
    if(dsu.connect(x, y) == 0) {
      dsu.unite(x, y);
      skeleton.push_back(i);
    }
  }
  return skeleton;
}
std::vector<int> level, far, state;
std::vector<std::vector<int>> g;

void dfs(int node, int parent) {
  for(int h = 0; h < g[node].size(); h++) {
    int id = g[node][h];
    int to = edges[id].first + edges[id].second - node;
    if(to != parent) {
      level[to] = level[node] + 1;
      far[to] = id;
      dfs(to, node);
    }
  }
}

void mark_skeleton(std::vector<int> &skeleton, int n) {
  g.resize(n);
  for(int i = 0; i < skeleton.size(); i++) {
    int id = skeleton[i];
    g[edges[id].first].push_back(id);
    g[edges[id].second].push_back(id);
  }
  dfs(0, -1); 
}

std::vector<int> with(std::vector<int> base, int val) {
  base.push_back(val);
  return base;
}

std::vector<int> without(std::vector<int> base, int val) {
  base.erase(std::find(base.begin(), base.end(), val));
  return base;
}

std::vector<int> exchange(std::vector<int> base, int val, int val2) {
  for(int i = 0; i < base.size(); i++)
    if(base[i] == val)
      base[i] = val2;
  return base;
}

void update(std::vector<int> &skeleton, int id) {
  int x = edges[id].first, y = edges[id].second;
  std::vector<int> path;
  if(level[x] < level[y])
    std::swap(x, y);
  while(level[x] != level[y]) {
    path.push_back(far[x]);
    x = edges[far[x]].first + edges[far[x]].second - x;
  }
  while(x != y) { 
    path.push_back(far[x]);
    x = edges[far[x]].first + edges[far[x]].second - x;
    path.push_back(far[y]);
    y = edges[far[y]].first + edges[far[y]].second - y;
  }
  bool chance = 0;
  for(int i = 0; i < path.size(); i++) { 
    int id2 = path[i];
    if(state[id2] == 0)
      chance = 1;
  }
  if(chance == 0)
    return ;
  int base = count_common_roads(skeleton);
  for(int i = 0; i < path.size(); i++) {
    int id2 = path[i];
    if(0 < state[id2]) {
      state[id] = state[id2] - base + count_common_roads(exchange(skeleton, id2, id));
      break;
    }
  }
  if(0 < state[id]) {
    for(int i = 0; i < path.size(); i++) {
      int id2 = path[i];
      if(0 == state[id2]) {
        state[id2] = state[id] - count_common_roads(exchange(skeleton, id2, id)) + base;
      }
    }
  } else {
    std::vector<int> eval(path.size());
    int smax = base;
    for(int i = 0; i < path.size(); i++) {
      int id2 = path[i];
      eval[i] = count_common_roads(exchange(skeleton, id2, id));
      smax = std::max(eval[i], smax);
    }
    if(smax == base)
      state[id] = 1;
    else
      state[id] = 2;
    for(int i = 0; i < path.size(); i++)
      if(smax == eval[i])
        state[path[i]] = 1;
      else
        state[path[i]] = 2;
  }
}

int eval(std::vector<int> aux, std::vector<int> &skeleton, int n){
  Dsu dsu(n);
  for(int i = 0; i < aux.size(); i++) 
    dsu.unite(edges[aux[i]].first, edges[aux[i]].second);
  int cost = 0;
  for(int i = 0; i < skeleton.size(); i++) {
    int id = skeleton[i];
    if(dsu.connect(edges[id].first, edges[id].second) == 0) {
      dsu.unite(edges[id].first, edges[id].second);
      aux.push_back(id);
      cost += state[id] - 1;
    }
  }

  return count_common_roads(aux) - cost;
}

std::vector<int> first_k(std::vector<int> aux, int k) {
  std::vector<int> result;
  for(int i = 0; i < k; i++)
    result.push_back(aux[i]);
  return result;
}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
  edges.resize(u.size());
  state.resize(u.size());
  far.resize(n);
  level.resize(n);

  for(int i = 0;i < edges.size(); i++)
    edges[i] = {u[i], v[i]};
  std::vector<int> skeleton = get_skeleton(n);
  mark_skeleton(skeleton, n);
  
  for(int i = 0; i < edges.size(); i++) 
    if(std::find(skeleton.begin(), skeleton.end(), i) == skeleton.end())
      update(skeleton, i);
  for(int i = 0; i < skeleton.size(); i++)
    if(state[skeleton[i]] == 0)
      state[skeleton[i]] = 2;
  

  std::vector<std::vector<int>> ad(n);
  for(int i = 0; i < u.size(); i++) {
    if(0 < state[i])
      continue;
    if(u[i] < v[i])
      ad[u[i]].push_back(i);
    else
      ad[v[i]].push_back(i);
  }

  for(int i = 0; i < n; i++) {
    int total = eval(ad[i], skeleton, n);
    for(int j = 0; j < total; j++) {
      int x = 0;
      for(int jump = (1 << 10); 0 < jump; jump /= 2) {
        if(x + jump <= ad[i].size() && eval(first_k(ad[i], x + jump), skeleton, n) <= j)
          x += jump;
      }
      state[ad[i][x]] = 2;
    }
  }


  std::vector<int> sol;
  for(int i = 0; i < u.size(); i++)
    if(state[i] == 2)
      sol.push_back(i);

  return sol;
}

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> get_skeleton(int)':
simurgh.cpp:40:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |   for(int i = 0; i < edges.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~
simurgh.cpp: In function 'void dfs(int, int)':
simurgh.cpp:54:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   for(int h = 0; h < g[node].size(); h++) {
      |                  ~~^~~~~~~~~~~~~~~~
simurgh.cpp: In function 'void mark_skeleton(std::vector<int>&, int)':
simurgh.cpp:67:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   for(int i = 0; i < skeleton.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> exchange(std::vector<int>, int, int)':
simurgh.cpp:86:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |   for(int i = 0; i < base.size(); i++)
      |                  ~~^~~~~~~~~~~~~
simurgh.cpp: In function 'void update(std::vector<int>&, int)':
simurgh.cpp:108:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |   for(int i = 0; i < path.size(); i++) {
      |                  ~~^~~~~~~~~~~~~
simurgh.cpp:116:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |   for(int i = 0; i < path.size(); i++) {
      |                  ~~^~~~~~~~~~~~~
simurgh.cpp:124:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |     for(int i = 0; i < path.size(); i++) {
      |                    ~~^~~~~~~~~~~~~
simurgh.cpp:133:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |     for(int i = 0; i < path.size(); i++) {
      |                    ~~^~~~~~~~~~~~~
simurgh.cpp:142:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |     for(int i = 0; i < path.size(); i++)
      |                    ~~^~~~~~~~~~~~~
simurgh.cpp: In function 'int eval(std::vector<int>, std::vector<int>&, int)':
simurgh.cpp:152:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |   for(int i = 0; i < aux.size(); i++)
      |                  ~~^~~~~~~~~~~~
simurgh.cpp:155:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |   for(int i = 0; i < skeleton.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:180:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  180 |   for(int i = 0;i < edges.size(); i++)
      |                 ~~^~~~~~~~~~~~~~
simurgh.cpp:185:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  185 |   for(int i = 0; i < edges.size(); i++)
      |                  ~~^~~~~~~~~~~~~~
simurgh.cpp:188:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  188 |   for(int i = 0; i < skeleton.size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~~
simurgh.cpp:194:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  194 |   for(int i = 0; i < u.size(); i++) {
      |                  ~~^~~~~~~~~~
simurgh.cpp:208:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  208 |         if(x + jump <= ad[i].size() && eval(first_k(ad[i], x + jump), skeleton, n) <= j)
      |            ~~~~~~~~~^~~~~~~~~~~~~~~
simurgh.cpp:217:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  217 |   for(int i = 0; i < u.size(); i++)
      |                  ~~^~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 19 / 19
• Subtask 5: 30 / 30