Submission #1195104

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195104		DeathIsAwe	Ideal city (IOI12_city)	C++20	100 / 100	131 ms	18568 KiB

city

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define ll long long
using namespace std;
const int modnum = 1000000000;
unordered_map<ll, int> gridmap;
unordered_map<int, int> blockmap;
ll total = 0;


ll ctoll(int a, int b) {
  return a*1000000000 + b;
}


int dfs(vector<vector<int>> &graph, vector<int> &blocksize, int node, int parent, int n) {
  pair<int,int> returnval;
  int siz = blocksize[node];
  for (int i : graph[node]) {
    if (i != parent) {
      siz += dfs(graph, blocksize, i, node, n);
    }
  }
  total += (ll)siz * (ll)(n - siz);
  total %= modnum;
  //cout << total << endl;
  return siz;
}


void solve(int n, int *x, int *y) {
  gridmap.clear();
  blockmap.clear();
  //cout << endl;
  for (int i=0;i<n;i++) {
    gridmap[ctoll(x[i], y[i])] = i;
    //cout << x[i] << ' ' << y[i] << endl;
  }
  //cout << endl;


  int xnum = 0, top, bottom;
  vector<int> blocksize(n);
  for (int i=0;i<n;i++) {
    if (blockmap.find(i) != blockmap.end()) continue;

    blocksize[xnum] = 0;
    top = y[i]; bottom = y[i];
    while (gridmap.find(ctoll(x[i], top)) != gridmap.end()) {
      blockmap[gridmap[ctoll(x[i], top)]] = xnum;
      //cout << x[i] << ' ' << top << ' ' << gridmap[ctoll(x[i], top)] << endl;
      top += 1; blocksize[xnum] += 1;
    }
    while (gridmap.find(ctoll(x[i], bottom)) != gridmap.end()) {
      blockmap[gridmap[ctoll(x[i], bottom)]] = xnum;
      //cout << x[i] << ' ' << bottom << ' ' << gridmap[ctoll(x[i], bottom)] << endl;
      bottom -= 1; blocksize[xnum] += 1;
    }
    //cout << endl;
    blocksize[xnum] -= 1;
    xnum += 1;
  }


  /*
  for (int i=0;i<n;i++) {
    cout << i << " : " << blockmap[i] << endl;
  }
  cout << endl;
  */


  vector<vector<int>> graph(n);
  unordered_set<ll> edges;
  for (int i=0;i<n;i++) {
    if (gridmap.find(ctoll(x[i] - 1, y[i])) != gridmap.end()) {
      if (edges.find(ctoll(blockmap[i], blockmap[gridmap[ctoll(x[i] - 1, y[i])]])) == edges.end()) {
        edges.insert(ctoll(blockmap[i], blockmap[gridmap[ctoll(x[i] - 1, y[i])]]));
        edges.insert(ctoll(blockmap[gridmap[ctoll(x[i] - 1, y[i])]], blockmap[i]));
        graph[blockmap[i]].pb(blockmap[gridmap[ctoll(x[i] - 1, y[i])]]);
        graph[blockmap[gridmap[ctoll(x[i] - 1, y[i])]]].pb(blockmap[i]);
        //cout << i << ' ' << gridmap[ctoll(x[i] - 1, y[i])] << ' ' << blockmap[i] << ' ' << blockmap[ctoll(x[i] - 1, y[i])] << endl;
      }
    } else if (gridmap.find(ctoll(x[i] + 1, y[i])) != gridmap.end()) {
      if (edges.find(ctoll(blockmap[i], blockmap[gridmap[ctoll(x[i] + 1, y[i])]])) == edges.end()) {
        edges.insert(ctoll(blockmap[i], blockmap[gridmap[ctoll(x[i] + 1, y[i])]]));
        edges.insert(ctoll(blockmap[gridmap[ctoll(x[i] + 1, y[i])]], blockmap[i]));
        graph[blockmap[i]].pb(blockmap[gridmap[ctoll(x[i] + 1, y[i])]]);
        graph[blockmap[gridmap[ctoll(x[i] + 1, y[i])]]].pb(blockmap[i]);
        //cout << i << ' ' << gridmap[ctoll(x[i] + 1, y[i])] << ' ' << blockmap[i] << ' ' << blockmap[ctoll(x[i] + 1, y[i])] << endl;
      }
    }
  }
  //cout << endl;


  /*
  for (int i=0;i<xnum;i++) {
    cout << i << " : ";
    for (int j: graph[i]) {
      cout << j << ' ';
    }
    cout << endl;
  }
  */


  dfs(graph, blocksize, 0, -1, n);
}



int DistanceSum(int n, int *x, int *y) {
  int minx = INT32_MAX, miny = INT32_MAX;
  for (int i=0;i<n;i++) {
    minx = min(minx, x[i]);
    miny = min(miny, y[i]);
  }
  for (int i=0;i<n;i++) {
    x[i] -= minx;
    y[i] -= miny;
  }


  solve(n, y, x);
  solve(n, x, y);
  return total % modnum;
}

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