Submission #170894

#	Time	Username	Problem	Language	Result	Execution time	Memory
170894		AlexLuchianov	Ideal city (IOI12_city)	C++14	100 / 100	968 ms	39928 KiB

city

#include <map>
#include <vector>
#include <algorithm>
#include <iostream>
#include <stack>
#include <unordered_map>

using ll = long long;

int const nmax = 100000;
int const modulo = 1000000000;

int const iplus[4] = {0, 0, 1, -1};
int const jplus[4] = {1, -1, 0, 0};

#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

struct Point{
  int x;
  int y;
  bool operator < (Point const &a) const{
    if(x != a.x)
      return x < a.x;
    else
      return y < a.y;
  }
};

void normalize(std::vector<Point> &v){
  int xmin = v[0].x, ymin = v[0].y;
  for(int i = 1; i < v.size(); i++){
    xmin = MIN(xmin, v[i].x);
    ymin = MIN(ymin, v[i].y);
  }
  for(int i = 0; i < v.size(); i++){
    v[i].x -= xmin;
    v[i].y -= ymin;
  }
}

std::map<std::pair<int,int>, int> cell;

namespace Dsu{
  int mult[1 + nmax];
  int sz[1 + nmax];

  void initialize(int n){
    for(int i = 0; i <= n; i++) {
      mult[i] = i;
      sz[i] = 1;
    }
  }
  int jump(int a){
    if(mult[a] != a)
      return jump(mult[a]);
    else
      return a;
  }
  void unite(int gala, int galb){
    gala = jump(gala);
    galb = jump(galb);
    if(sz[galb] < sz[gala])
      std::swap(gala, galb);
    if(gala != galb){
      mult[gala] = galb;
      sz[galb] += sz[gala];
    }
  }
}

std::vector<Point> line[1 + nmax];

std::map<Point, int> id;
std::unordered_map<int, int> leftextrem, leftextrem2;

int dp[1 + nmax], dp2[1 + nmax];
int cost[1 + nmax], seen[1 + nmax];

std::vector<int> g[1 + nmax];

void dfs(int node, int parent){
  //std::cout << node << " " << parent << '\n'
  seen[node] = 1;
  for(int h = 0; h < g[node].size(); h++){
    int to = g[node][h];
    if(to != parent) {
      dfs(to, node);
      cost[node] += cost[to];
    }
  }
}

int dfs2(int node, int parent, int total){
  int result = 1LL * (total - cost[node]) * cost[node] % modulo;

  for(int h = 0; h < g[node].size(); h++){
    int to = g[node][h];
    if(to != parent){
      result += dfs2(to, node, total);
      if(modulo <= result)
        result -= modulo;
    }
  }
  return result;
}

int solveline(int x){
  std::vector<int> nodes;

  //std::cout << "|";

  for(int i = 0; i < line[x].size(); i++){
    Point curr = line[x][i];
    g[id[curr]].clear();
    if(id[curr] == leftextrem[id[curr]]) {
      cost[id[curr]] = dp[id[curr]];
      nodes.push_back(id[curr]);
    }
  }

  for(int i = 0; i < line[x + 1].size(); i++){
    Point curr = line[x + 1][i];
    g[id[curr]].clear();
    if(id[curr] == leftextrem2[id[curr]]) {
      cost[id[curr]] = dp2[id[curr]];
      nodes.push_back(id[curr]);
    }
  }

  //std::cout << "%";

  int result = 0;
  for(int i = 0; i < line[x].size(); i++){
    Point curr = line[x][i];
    if(0 < cell[{x + 1, curr.y}] && (0 == cell[{x, curr.y - 1}] || 0 == cell[{x + 1, curr.y - 1}])) {
      int gala = leftextrem2[cell[{x + 1, curr.y}]], galb = leftextrem[id[curr]];

      g[galb].push_back(gala);
      g[gala].push_back(galb);
      //std::cout << "edge " << gala << " " << galb << '\n';
    }
  }
  //std::cout <<"^";

  for(int i = 0; i < nodes.size(); i++){
    int node = nodes[i];
    seen[node] = 0;
  }

 // std::cout << "%";

  for(int i = 0; i < nodes.size(); i++){
    int node = nodes[i];
    if(seen[node] == 0){
      dfs(node, -1);
     // std::cout << node << " " << cost[node] << '\n';
      result += dfs2(node, -1, cost[node]);

      if(modulo <= result)
        result -= modulo;
    }
  }

 // std::cout << ":" << x << " " << result << '\n' << '\n';

  return result ;
}


std::unordered_map<int,int> leftsmall;

int solve(std::vector<Point> v){
  int n = v.size();
  std::sort(v.begin(), v.end());
  for(int i = 0; i < n; i++)
    dp[i] = dp2[i] = 0;

  /*
  for(int i = 0; i < n; i++)
    std::cout << v[i].x << " " << v[i].y << '\n';
  std::cout << '\n';
  */

  leftextrem.clear();
  leftextrem2.clear();
  leftsmall.clear();

  id.clear();
  cell.clear();
  for(int i = 0; i < n; i++)
    line[i].clear();

  for(int i = 0; i < n; i++) {
    line[v[i].x].push_back(v[i]);
    id[v[i]] = i + 1;
  }
  Dsu::initialize(n);

  for(int i = 0; i < n; i++){
    for(int j = 0; j < line[i].size(); j++){
      Point curr = line[i][j];

      cell[{curr.x, curr.y}] = id[curr];
      if(0 < cell[{curr.x, curr.y - 1}])
        Dsu::unite(id[curr], cell[{curr.x, curr.y - 1}]);
      if(0 < cell[{curr.x - 1, curr.y}])
        Dsu::unite(id[curr], cell[{curr.x - 1, curr.y}]);
    }
    leftsmall.clear();
    for(int j = 0; j < line[i].size(); j++){
      Point curr = line[i][j];
      dp[id[curr]] = Dsu::sz[Dsu::jump(id[curr])];
      if(0 == leftsmall[Dsu::jump(id[curr])])
        leftsmall[Dsu::jump(id[curr])] = id[curr];

      leftextrem[id[curr]] = leftsmall[Dsu::jump(id[curr])];
    }
  }
 // std::cout << ":";
  Dsu::initialize(n);
  for(int i = n - 1; 0 <= i; i--){
    for(int j = 0; j < line[i].size(); j++){
      Point curr = line[i][j];
      cell[{curr.x, curr.y}] = id[curr];
      if(0 < cell[{curr.x, curr.y - 1}])
        Dsu::unite(id[curr], cell[{curr.x, curr.y - 1}]);
      if(0 < cell[{curr.x + 1, curr.y}])
        Dsu::unite(id[curr], cell[{curr.x + 1, curr.y}]);
    }

    leftsmall.clear();
    for(int j = 0; j < line[i].size(); j++){
      Point curr = line[i][j];
      dp2[id[curr]] = Dsu::sz[Dsu::jump(id[curr])];
      if(0 == leftsmall[Dsu::jump(id[curr])])
        leftsmall[Dsu::jump(id[curr])] = id[curr];

      leftextrem2[id[curr]] = leftsmall[Dsu::jump(id[curr])];
    }
  }

  int result = 0;
  for(int i = 0; i < n; i++) {
    result += solveline(i);
    if(modulo <= result)
      result -= modulo;
  }

  return result;
}

int DistanceSum(int N, int *X, int *Y) {
  std::vector<Point> v(N);
  //std::cout << '\n';
  for(int i = 0; i < N; i++) {
    v[i].x = X[i];
    v[i].y = Y[i];
  }
  normalize(v);

  int result = 0;
  result += solve(v);
  //return result;
  for(int i = 0; i < N; i++)
    std::swap(v[i].x, v[i].y);
  result = (result + solve(v)) % modulo;
  return result;
}

Compilation message (stderr)

city.cpp: In function 'void normalize(std::vector<Point>&)':
city.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 1; i < v.size(); i++){
                  ~~^~~~~~~~~~
city.cpp:36:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < v.size(); i++){
                  ~~^~~~~~~~~~
city.cpp: In function 'void dfs(int, int)':
city.cpp:85:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[node].size(); h++){
                  ~~^~~~~~~~~~~~~~~~
city.cpp: In function 'int dfs2(int, int, int)':
city.cpp:97:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[node].size(); h++){
                  ~~^~~~~~~~~~~~~~~~
city.cpp: In function 'int solveline(int)':
city.cpp:113:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < line[x].size(); i++){
                  ~~^~~~~~~~~~~~~~~~
city.cpp:122:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < line[x + 1].size(); i++){
                  ~~^~~~~~~~~~~~~~~~~~~~
city.cpp:134:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < line[x].size(); i++){
                  ~~^~~~~~~~~~~~~~~~
city.cpp:146:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < nodes.size(); i++){
                  ~~^~~~~~~~~~~~~~
city.cpp:153:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < nodes.size(); i++){
                  ~~^~~~~~~~~~~~~~
city.cpp: In function 'int solve(std::vector<Point>)':
city.cpp:201:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0; j < line[i].size(); j++){
                    ~~^~~~~~~~~~~~~~~~
city.cpp:211:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0; j < line[i].size(); j++){
                    ~~^~~~~~~~~~~~~~~~
city.cpp:223:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0; j < line[i].size(); j++){
                    ~~^~~~~~~~~~~~~~~~
city.cpp:233:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0; j < line[i].size(); j++){
                    ~~^~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45