Submission #170870

#	Time	Username	Problem	Language	Result	Execution time	Memory
170870		AlexLuchianov	Ideal city (IOI12_city)	C++14	23 / 100	868 ms	36968 KiB

city

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

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];

  struct Update{
    int x;
    int y;
    int szx;
    int szy;
  };
  std::stack<Update> st;

  void initialize(int n){
    for(int i = 0; i <= n; i++) {
      mult[i] = i;
      sz[i] = 1;
    }
    while(0 < st.size())
      st.pop();
  }
  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){
      st.push({gala, galb, sz[gala], sz[galb]});
      mult[gala] = galb;
      sz[galb] += sz[gala];
    }
  }
  void reset(){
    while(0 < st.size()){
      Update e = st.top();
      mult[e.x] = e.x;
      mult[e.y] = e.y;
      sz[e.x] = e.szx;
      sz[e.y] = e.szy;
      st.pop();
    }
  }
}

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

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

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){
  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){
  Dsu::reset();
  std::vector<int> nodes;

  for(int i = 0; i < line[x].size(); i++){
    Point curr = line[x][i];
    g[id[curr]].clear();
    if(0 == cell[{x, curr.y - 1}]) {
      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(0 == cell[{x + 1, curr.y - 1}]) {
      cost[id[curr]] = dp2[id[curr]];
      nodes.push_back(id[curr]);
    }
  }

  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 = leftextrem[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';
    }
  }

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

  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 ;
}

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;
  leftextrem.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];

      if(0 < cell[{curr.x, curr.y - 1}])
        leftextrem[id[curr]] = leftextrem[id[{curr.x, curr.y - 1}]];
      else
        leftextrem[id[curr]] = id[curr];

      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}]);
      }
    }
    for(int j = 0; j < line[i].size(); j++){
      Point curr = line[i][j];
      dp[id[curr]] = Dsu::sz[Dsu::jump(id[curr])];
    }
  }

  Dsu::reset();
  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}]);
    }
    for(int j = 0; j < line[i].size(); j++){
      Point curr = line[i][j];
      dp2[id[curr]] = Dsu::sz[Dsu::jump(id[curr])];
    }
  }

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

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

  return result;
}

int DistanceSum(int N, int *X, int *Y) {
  std::vector<Point> v(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:31:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 1; i < v.size(); i++){
                  ~~^~~~~~~~~~
city.cpp:35: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:104: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:116: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:131:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < line[x].size(); i++){
                  ~~^~~~~~~~~~~~~~~~
city.cpp:140:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < line[x + 1].size(); i++){
                  ~~^~~~~~~~~~~~~~~~~~~~
city.cpp:150:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < line[x].size(); i++){
                  ~~^~~~~~~~~~~~~~~~
city.cpp:160:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < nodes.size(); i++){
                  ~~^~~~~~~~~~~~~~
city.cpp:165: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:200:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0; j < line[i].size(); j++){
                    ~~^~~~~~~~~~~~~~~~
city.cpp:215: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:231:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0; j < line[i].size(); j++){
                    ~~^~~~~~~~~~~~~~~~

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